2/1 bit operation

对付unsigned int要把判断条件改为xx != 0而不是xx > 0
(n & -n)是找n的binary里最右面的1所代表的数
n - (n & -n)效果为减去n的二进制表示中最右边为1的bit
n + (n & -n)就是直接在最低位的1上做进位加法。

这道题第一次做，错误出在1000000...，这题因为是un-signed int，最高位= 1的情况稍微特殊点

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int num = 0;
        for (int i = 0; i < 32; ++i) {
            if ((n & (1 << i)) != 0) {
                num++;
            }
        }
        return num;
    }
}

or we can use java arithmetic right shift <<<,

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int num = 0;
        while(n != 0) {
            if ((n & 1) != 0) {
                num++;
            }
            n >>>= 1;
        }
        return num;
    }
}

Reverse Bits

注意shift rst的顺序，先shift，再赋值。

public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        int rst = 0;
        for (int i = 0; i < 32; ++i) {
            rst = rst << 1;
            if ((n & (1 << i)) != 0) rst += 1;
        }
        return rst;
    }
}

Counting Bits

how to do it like a boss?

Fenwick tree idea.

12 :..............0000001100
-12 :............11111110100
12 & -12:.....0000000100

So, n - (n & -n)效果为减去n的二进制表示中最右边为1的bit. 结果肯定比n小，bit数又一定只比n多一个，就可以迭代求解了~

public class Solution {
    public int[] countBits(int num) {

        int[] rst = new int[num + 1];
        for (int i = 1; i <= num; ++i) {
            rst[i] = rst[i - (i & -i)] + 1;
        }
        return rst;
    }
}

Power of X

power of 2

Given an integer, write a function to determine if it is a power of two.

At first, we know that powers of two must be larger than 0, but exponent would be negative or 0 or positive. Then, because the input is an Integer. so we don't need to consider negative exponent. In this problem, we have one corner case that should be processed. 100000... would be changed into -2147483648.

http://www.exploringbinary.com/the-powers-of-two/

There are several ways to do:

Bit operation:

If n is the power of two:

n = 2 ^ 0 = 1 = 0b0000...00000001, and (n - 1) = 0 = 0b0000...0000.
n = 2 ^ 1 = 2 = 0b0000...00000010, and (n - 1) = 1 = 0b0000...0001.

So we have n & (n-1) == 0b0000...0000 == 0, otherwise, n & (n-1) != 0.

class Solution {
    public boolean isPowerOfTwo(int n) {
        return n > 0 && ((n & (n - 1)) == 0);
    }
}

bitCount():

class Solution {
    public boolean isPowerOfTwo(int n) {
        return n > 0 && Integer.bitCount(n) == 1;
    }
}

count the 1 bits:

public boolean isPowerOfTwo(int n)
{
    if(n < 1) return false;
    int count = 0;
    while(n)
    {
        if(n & 1) count++;
        n >>= 1;
    }
    return count>1? false : true;
}

power of 3

因为3不是2的整数倍，用二进制的各种bit manipulation是没前途的。。不用循环解的话，要么log，要么mod.

log的解法是利用了log公式，如果不用log10的话会因为精度问题出错。(其实这个解法不管怎么说都需要考虑下numerial analysis提到过的精度问题。。)

idea is 去看下log3 n 是不是一个整数。

class Solution {
    public boolean isPowerOfThree(int n) {
        if (n <= 0) return false;

        double r = Math.log10(n) / Math.log10(3);
        if (r % 1 == 0) {
            return true;
        }
        return false;
    }
}

妖孽解法是。。1162261467 = 3^19，是整数中最大的power of 3，所以如果n是power of 3的话一定可以整除这个数。基本不会考。

power of 4

similar to power of 3, use log()

sajfkjks

Single Number

We can use Hash table to solve this problem with time complexity: O(n) space: O(n). But if it require space O(1). we need to consider Bit operation. Note, this is not the same as remove duplicate numbers in an array.

if we take XOR of zero and some bit, it will return that bit: a ^ 0 = a;

if we take XOR of two same bits, it will return 0: a ^ a = 0;

So, a ^ b ^ a = b;

class Solution {
  public int singleNumber(int[] nums) {
    int a = 0;
    for (int i : nums) {
      a ^= i;
    }
    return a;
  }
}

bit operation