数值问题¶

这部分都是一些数学几何计算方面的问题。主要由：

ipv4 转 int¶

比如： 127.0.0.1 ，转为 int 为 (01111111 00000000 00000000 00000001)

思路：

int toInt(){

}

那么，int 转 ipv4 如何解呢？

题目：输入一个整数，求该整数的二进制表达中有多少个 1。例如输入 10，由于其二进制表示为 1010，有两个 1，因此输出 2。

分析：这是一道很基本的考查位运算的面试题。解法 1：一轮循环移位计数（移位运算比除法运算效率要高,注意要考虑是负数的情况）解法 2：位运算解法 3：num &= num-1 巧妙之处在于，对高位没有影响。不断做 num &= num-1 直到 num=0。

1010 & 1001 = 1000 1000 * 0111 = 0000

int one_appear_count_by_binary(int num){
    int count = 0;
    while(num !=0 ){
        num &=  num-1;
        count++;
    }
    return count;
}

分析：

char *integer_to_hex(long i); //eg: 20 => 14
char *integer_to_bin(long i); //eg: 20 => 10100

注意，转 16 进制中，要判断 tmp[i] 是否是有符号的数

tmp[i] = tmp[i]>=0 ? tmp[i] : tmp[i]+16;

分析：

#define min(a,b) （(a)>(b)?(a):(b)）
#define MIN(A,B) ({ __typeof__(A) __a = (A); __typeof__(B) __b = (B); __a < __b ? __a : __b; })

这里不能使用比较符号：

#define min(a,b) ((a)-(b) & (0x1<<31))?(a):(b)

歌德巴赫猜想说任何一个不小于 6 的偶数都可以分解为两个奇素数之和。对此问题扩展，如果一个整数能够表示成两个或多个素数之和，则得到一个素数和分解式。

对于一个给定的整数，输出所有这种素数和分解式。注意，对于同构的分解只输出一次（比如 5 只有一个分解 2 + 3，而 3 + 2 是 2 + 3 的同构分解式

例如，对于整数 8，可以作为如下三种分解：

(1) 8 = 2 + 2 + 2 + 2
(2) 8 = 2 + 3 + 3
(3) 8 = 3 + 5

题目：输入数字 n，按顺序输出从 1 最大的 n 位 10 进制数。比如输入 3，则输出 1、2、3 一直到最大的 3 位数即 999。

分析：这是一道很有意思的题目。看起来很简单，其实里面却有不少的玄机。输入 4，输出: 1,2,3,。。9999 输入 5，输出: 1,2,3,4,...99999

玄机一: 整数溢出

我们把只包含因子 2、3 和 5 的数称作丑数（Ugly Number）。例如 6、8 都是丑数，但 14 不是，因为它包含因子 7。习惯上我们把 1 当做是第一个丑数。分析：这是一道在网络上广为流传的面试题，据说 google 曾经采用过这道题。

求按从小到大的顺序的第 1500 个丑数。

这里的因子应该不包含本身,因此这个序列应该是这样： 1,2,3,4,5,6,8,9,10,12,15,16,18,20,28....

1）所有的偶数都在序列中 2）3 的倍数也在序列中 3）5 的倍数也在系列中

第 1500 个： 1500/22=68 余 4，一个周期内的前 4 个数是 2，3，4，5；最终答案是 68*30+5