需要熟练掌握一些常见功能的位操作实现，具体为：

<1> 常用的等式：-n = ~(n-1) = ~n+1

<2> 获取整数n的二进制中最后一个1：n&(-n) 或者 n&~(n-1)，如：n=010100，则-n=101100，n&(-n)=000100

<3> 去掉整数n的二进制中最后一个1：n&(n-1)，如：n=010100，n-1=010011，n&(n-1)=010000

（1） 加法实现

可以很容易地用“异或”和“或”操作实现整数加法运算：对应位数的“异或操作”可得到该位的数值，对应位的“与操作”可得到该位产生的高位进位，如：a=010010，b=100111，计算步骤如下：

第一轮：a^b=110101，(a&b)<<1=000100， 由于进位（000100）大于0，则进入下一轮计算，a=110101，b=000100，a^b=110001，(a&b)<<1=001000，由于进位大于0，则进入下一轮计算：a=110001，b=001000，a^b=111001，(a&b)<<1=0，进位为0，终止，计算结果为：111001。

代码如下：

int add(inta, intb) {
  int carry, add;
  do{
    add = a ^ b;
    carry = (a & b) << 1;
    a = add;
    b = carry;
  }while(carry != 0);
  return add;
}

（2） 减法实现

减法可很容易地转化为加法：a - b = a + (-b) = a + (~b + 1 )

代码如下：

int subtract(inta,intb) {
  returnadd(a, add(~b, 1));
}

（3） 乘法实现

先看一个实例：1011*1010：

1011
   * 1010
 ----------
    10110 < 左移一位，乘以0010
+ 1011000 < 左移3位，乘以1000
----------
  1101110

因而乘法可以通过系列移位和加法完成。最后一个1可通过b&~(b-1)求得，可通过b& (b-1)去掉，为了高效地得到左移的位数，可提前计算一个map，代码如下：

（4） 除法实现

乘法可很容易转化为减法操作，主要思想与乘法实现类似，代码如下：

int divide(inta, intb) {
  boolneg = (a > 0) ^ (b > 0);
  if(a < 0)
    a = -a;
  if(b < 0)
    b = -b;
  if(a < b)
    return0;
  intmsb = 0;
  for(msb = 0; msb < 32; msb++) {
    if((b << msb) >= a)
      break;
  }
  intq = 0;
  for(inti = msb; i >= 0; i--) {
    if((b << i) > a)
      continue;
    q |= (1 << i);
    a -= (b << i);
  }
  if(neg)
    return-q;
  returnq;
}

原创文章，转载请注明： 转载自新书《程序员面试笔试宝典》官网

本文链接地址: 位操作实现加减乘除四则运算

获取一个正整数的最高位和更高一位值

http://blog.csdn.net/zhengdan66/article/details/8929310

一个正整数值采用Integer.highestOneBit(n)可以获取最高位，代码为：
public static int prevPowerOf2(int n) {
if (n <= 0)
throw new IllegalArgumentException();
return Integer.highestOneBit(n);
}
highestOneBit(int i)
{
i |= (i >>> 1);//右移过程使用零扩展
i |= (i >>> 2);
i |= (i >>> 4);
i |= (i >>> 8);
i |= (i >>> 16);
return i ^ (i >>> 1);
}
执行完i|=(i>>>1)后，最高位1的右边也成为1
执行i|=(i>>>2)后，最高位1右边的1+2=3位以内都成为1
执行i|=(i>>>4)后，最高位1右边的1+2+4=7位以内都成为1
......
执行i|=(i>>>16)后，最高位1右边的1+2+4+8+16=31位以内都成为1
i^(i>>>1)即可将最高位1右边的1都置为0

public static int nextPowerOf2(int n) {
if (n <= 0 || n > (1 << 30))
throw new IllegalArgumentException();
n -= 1;
n |= n >> 16;
n |= n >> 8;
n |= n >> 4;
n |= n >> 2;
n |= n >> 1;
return n + 1;
}