BitMagic

#逆转比特位

给定数字n，求颠倒每一位bit后产生的结果。

1. 循环移位

   unsigned int count = sizeof(int)*8
   unsigned int reverse_num = 0
   while num != 0:
       reverse_num |= (n & 1)<<count;
       n >>= 1;
       --count;
   return reverse_num

1. 二分
   两两之间、再求四四之间、递进求到16进行互相的交换

   n = (((n & 0x55555555)<<1) | ((n>>1) & 0x55555555));
   n = (((n & 0x33333333)<<2) | ((n>>2) & 0x33333333));
   n = (((n & 0x0f0f0f0f)<<4) | ((n>>4) & 0x0f0f0f0f));
   n = (((n & 0x00ff00ff)<<8) | ((n>>8) & 0x00ff00ff));
   n = (((n & 0x0000ffff)<<16) | ((n>>16) & 0x0000ffff));
   return n;

对于数字的移位操作，需要保证数字是无符号整数，否则可能是算数移位 或者 逻辑移位，依赖于具体的实现。

#整数二进制中1的数量

1. n & (n-1) 去掉最低1

   while n:
       c += 1
       n & = n-1

2. n & (-n) 得到最低位1

   while n:
       c += 1
       n -= n & (-n)

3. 二分
   和Reverse Bit方法类似，先求两两之间、再求四四之间、递进求到16求1的数目

   n = (n & (0x55555555)) + ((n >> 1) & 0x55555555)
   n = (n & (0x33333333)) + ((n >> 2) & 0x33333333)
   n = (n & (0x0f0f0f0f)) + ((n >> 4) & 0x0f0f0f0f)
   n = (n & (0x00ff00ff)) + ((n >> 8) & 0x00ff00ff)
   n = (n & (0x0000ffff)) + ((n >> 16) & 0x0000ffff)
   return n

#Next Power of 2
通过n & (n-1) 获取最高位，再左移一位即可，注意检查是否为0:

next_pow = n & (n-1)
if next_pow == 0:
    return n
return next_pow << 1

#A * B 不能用乘法，除法

res = 0
isNeg = (a > 0 and b < 0) or (a < 0 and b > 0)
for i in range(63):
    if ((b >> i) & 1) > 0:
        tmp = res + (a << i) #考虑是否越界
        if tmp < res:
            return isNeg ? MIN_INT : MAXINT
        res = tmp
return res

#A / B 不能用乘法，除法

res = 0
isNeg = (a > 0 and b < 0) or (a < 0 and b > 0)
while a >= b:
    power = 1
    while ((b<<power) >= (b<<(power-1))) and (b<<power) <= a:
        power += 1
    res |= 1<<(power-1)
    a -= (b<<(power-1))
if isNeg:
    res *= -1