bit manipulation

reference: http://www.cnblogs.com/maples7/p/4324844.html

• for clause judges the each bit in a 16-bit binary number.
• In the for loop, we use & and <<. The effect of << operation is like this: when i = 15, (1 << i) will convert 0000000000000001 into 1000000000000000; and when i = 10, the result will be 0000010000000000. So the result of num &（1 << i is comparing the ith digit (i is from 0 to 15) in num with (1 << i). Only when ith digit in num is 1, can num &（1 << i） be true.

1
2
3
4
5
6
7
8
9
10
11
12

public String (int num) {
    StringBuilder result = new StringBuilder();
    
    for (int i = 15; i >= 0; i--) {
        if ((num & (1 << i)) != 0) {
            result.append(1);
        } else {
            result.append(0);
        }
    }
    return result.toString();
}

LeetCode Example 1 - Number of 1 Bits

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

Write a function that takes an unsigned integer and returns the number of 1 bits it has (also known as the Hamming weight).

For example, the 32-bit integer 11 has binary representation 00000000000000000000000000001011, so the function should return 3.

Solution 1

1
2
3
4
5
6
7
8
9
10
11
12
13

public class Solution {
    
    public int hammingWeight(int n) {
        int count = 0;
        for (int i = 0; i < 32; i++) {
            if ((n & (1 << i)) != 0) {
                count ++;
            }
        }
        
        return count;
    }
}

Solution 2 O(logN)

1
2
3
4
5
6
7
8
9
10
11
12
13

public class Solution {
    
    public int hammingWeight(int n) {
        int count = 0;
        
        while(n > 0) {
            count += (n & 1);
            n >> 1
        }
        
        return count;
    }
}

Solution 3 O(countOnes(N))

1
2
3
4
5
6
7
8
9
10
11
12
13

public class Solution {
    
    public int hammingWeight(int n) {
        int count = 0;
        
        while(n > 0) {
            count ++;
            n &= n - 1
        }
        
        return count;
    }
}

LeetCode Example 2 - Reverse Bits

https://leetcode.com/problems/reverse-bits/

Reverse bits of a given 32 bits unsigned integer.

For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as 00111001011110000010100101000000).

Follow up:
If this function is called many times, how would you optimize it?

1
2
3
4
5
6
7
8
9
10
11
12

public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        int result = 0;

        for (int i = 0; i < 32; i++) {
            result = (result << 1) | (n & 1);
            n = n >> 1;
        }
        return result;
    }
}