[bit manipulation] 476. Number Complement

Given a positive integer, output its complement number. The complement strategy is to flip the bits of its binary representation.

Note:
The given integer is guaranteed to fit within the range of a 32-bit signed integer.
You could assume no leading zero bit in the integer’s binary representation.
Example 1:
Input: 5
Output: 2
Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.
Example 2:
Input: 1
Output: 0
Explanation: The binary representation of 1 is 1 (no leading zero bits), and its complement is 0. So you need to output 0.

~num取反 但是把所有leading 0都跟着取反了。例如5: 101, ~5 不是010, 是1111..010。
所以制作一个mask,111, 使~num & mask即可。
如何制作mask?一个可以到处用的trick:

(Integer.highestOneBit(num) << 1) – 1

例如5,Integer.highestOneBit(num) = 0b100, 右移一位变成 1000,再减1变成111

[bit manipulation] 421. Maximum XOR of Two Numbers in an Array

Given a non-empty array of numbers, a0, a1, a2, … , an-1, where 0 ≤ ai < 231.

Find the maximum result of ai XOR aj, where 0 ≤ i, j < n. Could you do this in O(n) runtime? Example: Input: [3, 10, 5, 25, 2, 8] Output: 28 Explanation: The maximum result is 5 ^ 25 = 28. 分别计算每一位应该是什么

 public int findMaximumXOR(int[] nums) {        int max = 0, mask = 0;        for (int i = 31; i >= 0; i--) { //从最重要的位MSB看起
           mask = mask | 1 << i; // 每次只看一位,用mask控制看哪位
           Set<Integer> set = new HashSet();
           for (int num : nums) {
               set.add(num & mask); //记录所有nums在这一位是什么情况
           }
           int tmp = max | (1 << i); //结果在当前位暂时设为1
           for (int prefix : set) {
               if (set.contains(tmp ^ prefix)) {
                   max = tmp; //如果有在这一位有和max不同的,那么max在这一位就真的可以是1
                   break;
               }
           }
       }
       return max;

    }

[bit manipulation]477. Total Hamming Distance

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Now your job is to find the total Hamming distance between all pairs of the given numbers.

Example:
Input: 4, 14, 2

Output: 6

Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just
showing the four bits relevant in this case). So the answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.
Note:
Elements of the given array are in the range of 0 to 10^9
Length of the array will not exceed 10^4.

Brute force: time limit exceed
思路:integer一共32位, int[] count = new int[32]记录每个bit一共在几个数字中on(一共n = nums.length个数字)。对于一个bit,on的次数 k 次,off的次数 n-k 次,则对于total distance的贡献是 k * (n-k),因为每一个(on, off)的组合都会给total distance加1.

    public int totalHammingDistance(int[] nums) {
        int N = nums.length;
        int[] count = new int[32]; // count for when the bit is on
        for (int n : nums) {
            int i = 0;
            while (n > 0) {
                count[i++] += n & 1;
                n >>= 1;
            }
        }
        
        int total = 0;
        for (int i = 0; i < 32; i++) {
            total += count[i] * (N - count[i]);
        }
        return total;
    }

[LC 371]. Sum of Two Integers

Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.

位运算总结:

全的 https://discuss.leetcode.com/topic/50315/a-summary-how-to-use-bit-manipulation-to-solve-problems-easily-and-efficiently
加减 https://discuss.leetcode.com/topic/49771/java-simple-easy-understand-solution-with-explanation/2

位运算做数学运算

Set union A | B
Set intersection A & B
Set subtraction A & ~B
Set negation ALL_BITS ^ A or ~A
Set bit A |= 1 << bit
Clear bit A &= ~(1 << bit)
Test bit (A & 1 << bit) != 0
Extract last bit A&-A or A&~(A-1) or x^(x&(x-1))
Remove last bit A&(A-1)
Get all 1-bits ~0

加:

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;
}

减:

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

	return a;
}

取反:

public int negate(int x) {
	return ~x + 1;
}