春节过完了,就从一篇博客开始新一年的码农生涯吧,最近在刷LintCode的题目,在做一道通过位运算实现加减法的题目时,顺便温习了Java位运算的内容,通过本文记录一下。计算机只有0和1,一切都只能用二进制表示,先来弄明白Java是如何表示十进制的数字的,Java用原码表示正数,用补码表示负数,也叫Two's Complement,补码为原码按位取反后+1,比如 15的二进制表示为0001111，-15的二进制表示为11110001,如果最高位为0,则表示正数,最高位为1则表示负数,Java支持的位运算操作符包括
The unary bitwise complement operator "~"
The signed left shift operator "<<" shifts a bit pattern to the left
the signed right shift operator ">>" shifts a bit pattern to the right
The unsigned right shift operator ">>>" shifts a zero into the leftmost position
The bitwise & operator performs a bitwise AND operation.
The bitwise ^ operator performs a bitwise exclusive OR operation.
The bitwise | operator performs a bitwise inclusive OR operation.
分别解释一下
~ 按位取反
<< 左移
>> 带符号补位右移
>>> 不带符号补位右移
&与
|或
^异或,不同为1,相同为0
位运算加减法a+b a&b后<<1 可以算出进位carry,通过a ^ b 可以算出不带进位后相加的值,再将carry相加,直到carry为0。
递归实现。
public int addThroughBitOperationRecusioin(int a ,int b){
int carry = a & b;
int result = a ^ b;
while(carry != 0){
carry = carry << 1;
result = addThroughBitOperationRecusioin(carry,result);
carry = 0;
}
return result;
}
非递归实现
public void addThroughBitOperation(int a ,int b){
int carry = a & b;
System.out.println("carry " + Integer.toBinaryString(carry));
int result = a ^ b;
System.out.println("result " + Integer.toBinaryString(result));
while(carry != 0){
carry = carry << 1;
System.out.println("carry " +Integer.toBinaryString(carry));
int carryTemp = carry & result;
System.out.println("carry " + Integer.toBinaryString(carry));
result = carry ^ result;
System.out.println("result " + Integer.toBinaryString(result));
carry = carryTemp;
}
System.out.println(result);
}
参考资料
https://docs.oracle.com/javase/tutorial/java/nutsandbolts/op3.html
