Bit Manipulation

bit manipulation

Basic Operations

左移操作 A << B
右移操作 A >> B, A >>> B
按位与操作 A & B
按位或操作 A | B
按位非操作 ~A
异或操作 A ^ B, 异或操作也就是不进位加法，比如1 + 1 = 10， 我们只取个位，不要进位的那个1，其他同理。

two's complement: -x = ~x + 1

Tricks

http://www.jiuzhang.com/tutorial/bit-manipulation/84

• n & (n-1) remove last 1 in binary

https://leetcode.com/problems/power-of-two/description/ https://leetcode.com/problems/number-of-1-bits/description/

• determine odd/even: n % 2 or n & 1, n & 1 is better, unsigned integer can be larger than Integer.MAX_VALUE

• get last bit: x & -x

+, -, *, / operations

// Iterative
public int getSum(int a, int b) {
    if (a == 0) return b;
    if (b == 0) return a;

    while (b != 0) {
        int carry = a & b;
        a = a ^ b;
        b = carry << 1;
    }

    return a;
}

// Iterative
public int getSubtract(int a, int b) {
    while (b != 0) {
        int borrow = (~a) & b;
        a = a ^ b;
        b = borrow << 1;
    }

    return a;
}

// Recursive
public int getSum(int a, int b) {
    return (b == 0) ? a : getSum(a ^ b, (a & b) << 1);
}

// Recursive
public int getSubtract(int a, int b) {
    return (b == 0) ? a : getSubtract(a ^ b, (~a & b) << 1);
}

// Get negative number
public int negate(int x) {
    return ~x + 1;
}