Bit Hack Misc

http://blog.csdn.net/morewindows/article/details/7354571
变换符号只需要取反后加1即可

1. int SignReversal(int a)  
2. {  
3.     return ~a + 1;  
4. }  

求绝对值

1. int my_abs(int a)  
2. {  
3.     int i = a >> 31;  
4.     return i == 0 ? a : (~a + 1);  
5. }  

对于任何数，与0异或都会保持不变，与-1即0xFFFFFFFF异或就相当于取反。因此，a与i异或后再减i（因为i为0或-1，所以减i即是要么加0要么加1）也可以得到绝对值。所以可以对上面代码优化下：

1. int my_abs(int a)  
2. {  
3.     int i = a >> 31;  
4.     return ((a ^ i) - i);  
5. } 

三． 位操作与空间压缩
要压缩素数表的空间占用，可以使用位操作

http://segmentfault.com/a/1190000003789802

> 不用额外的变量实现两个数字互换。

def swap(num_1, num_2):
    num_1 ^= num_2
    num_2 ^= num_1
    num_1 ^= num_2
    return num_1, num_2

证明很简单，我们只需要明白异或运算满足下面规律：

• 0^a = a;
• a^a = 0;
• a^b^c = a^c^b;

巧妙运用异或可以高效解决很多问题，比如 找出数组中只出现了一次的数（除了一个数只出现一次外，其他数都是出现两次），以及它的升级版：数组中只出现1次的两个数字(百度面试题)。

> 不用判断语句来实现求绝对值。

def bit_abs(num):
    negative = num >> 31
    return (num ^ negative) - negative

这里假设程序运行环境中操作系统为32位，int型整数(不考虑整数溢出)用32位存储，因此可以用 num>>31 取出符号位，后面的部分留给大伙证明。

Divide two integers without using multiplication, division and mod operator.

就是说不用乘法，除法，求模运算来实现两个整数相除，看起来很简单，我可以用除数减去被除数，直到除数小于被除数，记录减法操作的次数即可。假设是计算m/n，那么时间复杂度为O(m/n)。用Python实现后，Time Limit Exceeded。我们考虑有没有更加优化的算法呢？

我们对除数减去被除数的过程稍作改进。假设求m/n，我们不一次次的 m-n，而是找到n的一个倍数，使得m-x*n尽可能小，这样能减少循环减法的次数，进而提高效率。我们知道在按位操作中，n << k相当于 n * 2^k，因此可以用2^k 来找合适的x。

我们需要这样的一个数字k，它使得n 2^k < m < n 2^(k+1)， 然后用m - n*2^k，得到新的m'。再找相应的k'，做减法，如此循环即可

http://brokendreams.iteye.com/blog/2084088
要求不用加减符号(包括负号)来实现加减法。
第1位的值有4种，0+0=0、1+0=1、0+1=1、1+1=0，这正好符合“异或”的情况。 
        第2位的值来自于第一位的进位加上本身的值，进位的情况也有4种，0+0=0、1+0=0、0+1=0,1+1=1，这正好符合“与”的情况。 
        考虑一般性，a+b就等同于a^b + (a&b) << 1，而这又是一个加法，可递归求解，出口就是当进位为0的时候。

1. public static int add(int a, int b){  
2.         return b == 0 ? a : add(a ^ b ,(a & b) << 1);  
3.     }  

那么减法怎么搞呢？减法也能用加法表示嘛，比如a-b就等于a+(-b)，但不能出现负号，我们知道Java中整型数值编码方式为补码，所以一个数对应的负数就这个数“取反加1”，

1. public static int sub(int a, int b){  
2.         return add(a, add(~b, 1));  
3.     }  

http://codesam.blogspot.com/2011/01/bit-manipulation-tips-and-tricks-part-1.html
1. Multiply a number by a power of two using bit left shift

a << b = a * 2^b

2. Divide a number by a power of two using bit right shift

a >> b = a / 2^b

3. Toggle a specified bit in a bit string without effecting other bits

bit_string = bit_string ^ (1 << positionOfBitToToggle)

4. Checking if a bit is on or off without affecting other bits

int isAvailable (int bitString, int targetNum)
{
  return bit_string & (1 << targetNum);
}

http://codesam.blogspot.com/2011/01/bit-manipulation-tips-tricks-part-2.html
1. Turning a bit off without affecting other bits

turnBitOff (int bitString, int bitPosition)
{
  return bitString & ~(1 << bitPosition);
}

2. Turning a bit on without affecting other bits

turnBitOn (int bitString, int bitPosition)
{
  return bitString || (1 << bitPosition);
}

http://www.1point3acres.com/bbs/thread-73742-1-1.html
再准备面试的时候总结了一下关于bit manipulation可能用到的东西。在这里和大家分享一下～
x ^ 0s = x      x & 0s = 0   x | 0s = x
x ^ 1s = ~x   x & 1s = x    x | 1s = 1s
x ^ x  = 0      x & x = x     x | x  = x

boolean getBit(int i, int num){
        return ( (num & (1 << i)) != 0 );
}

int setBit(int i, int num){
        return num | (1 << i);
}

int clearBit(int num, int i) {
        int mask = ~(1 << i);
        return num & mask;
}

int clearBitMSBthroughI(int num, int i){
        int mask = (1<< i) -1;
        return num & mask;
}

int clearBitsIThrough0(int i, int num) {
        int mask = ~( (1 << (i+1) )  -1 );
        return num & mask;
}

int updateBit(int i, int num, int v){
        int mask = ~(1 << i);
        return (num & mask) | (v << i);
}
http://blog.csdn.net/earthma/article/details/46762943

值为1且最靠右的位元置为0 (如果存在): 0101 1110 => 010 1100 : x&(x-1)

值为0且最靠右的位元置为1 (如果存在): 0101 1110 => 010 1111 : x|(x+1)

将尾部的所有连续的1置为0(如果存在): 0101 0111 => 0101 0000 : x&(x+1)

将尾部的所有连续的0置为1(如果存在): 0101 1000 => 0101 1111 : x|(x-1)

将最靠右的0置为1(如果存在)，且其他位元置为0: 0101 0111 => 0000 1000 :  ~x&(x+1)

将最靠右的1置为0(如果存在)，且其他位元置为1: 0101 1000 => 1111 0111 : ~x|(x-1)

将尾部的连续0置为1(如果存在)，且其他位元置为0: 0101 1000 => 0000 0111 : ~x&(x-1) or ~(x|-x) or (x&-x)-1

将尾部的连续1置为0(如果存在)，且其他位元置为1: 0101 0111 => 1111 1000 : ~x|(x+1)

保留最右的1(如果存在)，其他位元置为1: 0101 1000 => 0000 1000 :x&(-x)

最靠右的1及其右边的位元置为1，左边置为0: 0101 1010 => 0000 1111 : x^(x-1)

最靠右的0及其右边的位元置为1，左边置为0: 0101 1010 => 0000 0111 : x^(x+1)

右侧首个连续的1置为0: 0101 1100 => 0100 0000 (((x|(x-1))+1&x)  or ((x&-x)+x)&x

进阶：

求比某个数大且位元1的个数相同的数 例如 xxx0 1111 0000 => xxx1 0000 0111

令 x = xxx0 1111 0000

s = x&-x

r = s+x

y = r | ( ( x ^ r ) << 2 / s)

两数的平均数：

(x&y) + ((x^y)>>1) 下取整

(x|y)   - ((x^y)>>1) 上取整

统计位元‘1’的个数：

1.二分搜索法：

x = (x & 0x5555 5555) + ((x>>1) & 0x5555 5555)

x = (x & 0x3333 3333) + ((x>>2) & 0x3333 3333)

x = (x & 0x0F0F 0F0F) + ((x>>4) & 0x0F0F 0F0F)

x = (x & 0x00FF 00FF) + ((x>>8) & 0x00FF 00FF)

x = (x & 0x0000 FFFF) + ((x>>16) & 0x0000 FFFF)

例举一个八位数：

x = 1 0 1 1 1 1 0 0  

x1 = 01 10 10 00

x2 = 0011 0010

x3 = 00000101 = 5

上述代码中有多余的与操作

可以写成如下简单代码：

int pop(unsigned x){

x = x - ((x>>1) & 0x5555 5555)

x = (x & 0x3333 3333) + ((x>>2) & 0x3333 3333)

x = (x+(x>>4)) & 0x0F0F 0F0F

x = x+(x>>8)

        x = x + (x>>16)

return x& 0x0000 003F

}

第一行中x的值是由以下公式而来：

pop(x) =  x - [x/2] - [x/4]-···-[x/2^31]