Math and Bit

Summary

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

Example

Count the number of ones in the binary representation of the given number

int count_one(int n) {
    while(n != 0) {
        n = n & (n-1);
        count++;
    }
    return count;
}

SUM OF TWO INTEGERS

Use ^ and & to add two integers

int getSum(int a, int b) {
    return b==0? a:getSum(a^b, (a&b)<<1); //be careful about the terminating condition;
}

MISSING NUMBER

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array. For example, Given nums = [0, 1, 3] return 2. (Of course, you can do this by math.)

int missingNumber(int[] nums) {
    int ret = 0;
    for(int i = 0; i < nums.length; i++) {
        ret ^= i;
        ret ^= nums[i];
    }
    return ret^=nums.length();
}

REVERSE BITS

Reverse bits of a given 32 bits unsigned integer.

int reverse(int n) {
    int mask = 1, result = 0;
    for(int i = 0; i < 32; i++) {
        result <<= 1;
        if(mask & n != 0) result |= 1;
        mask <<= 1;
    }
}

找不同的元素 Find the difference

java异或操作 a ^ b

a^b^b =a

389. Find the Difference

because a ^ a ^ b = b and b ^ 0 = b, so we can use XOR operator all the char in both s and t, then the remind char is the new one.

136. Single Number

一个数异或自己，得到的是0 一个数异或0，得到的是自己。

The basic idea is to use XOR operation. We all know that a^b^b =a, which means two xor operations with the same number will eliminate the number and reveal the original number.

count bits (一个数字的二进制表达中有几个1)

401. Binary Watch

how many possible way binary number can represent under the case of given number of bits?

The main idea is to traversal from 0 to 59 find out each number represended by how many bits. If the number of bits is equals to the given number, we can record this moment.

public List<String> readBinaryWatch(int num) {
    List<String> result = new ArrayList<>();

    for(int i = 0; i < 12; i++) {
        for(int j = 0; j < 60; j++) {
            int count = countBit(i) + countBit(j);
            if(num == count) {
                String s = "";
                s += i + ":";

                if(j < 10) {
                    s += "0" + j;
                } else {
                    s += j;
                }
                result.add(s);
            }
        }
    }

    return result;
}

// count bit
public int countBit(int num) {
    int result = 0;

    while(num > 0) {
        if((num & 1) == 1) {
            result++;
        }
        num >>= 1;
    }

    return result;
}

& trick

231. Power of Two

If a number is power of 2, then its highly bit is 1 and there is only one 1. Therefore, n & (n-1) is 0.

return n > 0 && (n & (n - 1) == 0);

shift bits

190. Reverse Bits

原数不断右移取出最低位，赋给新数的最低位后新数再不断左移。

keeping shift right of number to get the lowest bit, assign to the result being lowest bit, then shift left.

If this function is called many times, how would you optimize it? Cacheing it and divide to four part to conquer.

Maximum Product of Word Lengths

这道题最直接的想法就是，两两字符串来比较，如果没有重复的字符就去计算他们的长度之积。 用一个hashset去记录每个字符是否出现。

如何去提高速度？

用bit mask 来记录某个字符是否出现过。 原理是一个int 有32位，可以表示26个字母。如果这个字母出现过，那么就把这一位变成1.

如果两个单词的字母全不一样，那么他们相互与的结果一定是0.

mask |= 1 << (c - 'a')

Bitwise and Bit Shift Operators

">>" is signed because it keeps the sign. It uses the most left digit in binary representation of a number as a filler.

">>>" is unsigned version of this operator. It always use zero as a filler:

The unary bitwise complement operator "~" inverts a bit pattern; it can be applied to any of the integral types, making every "0" a "1" and every "1" a "0".

For example, a bytecontains 8 bits; applying this operator to a value whose bit pattern is "00000000" would change its pattern to "11111111".

^ is XOR can use for bit plus