Java位运算

春节过完了,就从一篇博客开始新一年的码农生涯吧,最近在刷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

https://www.cs.cornell.edu/~tomf/notes/cps104/twoscomp.html