Bit Manipulation，数 '1' bits
对付 unsigned int 要把判断条件改为 xx != 0 而不是 xx > 0
(n & -n) 是找 n 的 binary 里最右面的 1 所代表的数
n - (n & -n) 效果为减去 n 的二进制表示中最右边为 1 的 bit
n + (n & -n) 就是直接在最低位的 1 上做进位加法。
max Integer: 2^31-1; 0111...1;
min Integer: -2^31;1000...000
all 1:
正数的补码就是其本身
负数的补码是在其原码的基础上, 符号位不变, 其余各位取反, 最后+1. (即在反码的基础上+1)
[+1] = [00000001]原= [00000001]反= [00000001]补
[-1] = [10000001]原= [11111110]反= [11111111]补
Number of 1 Bits
这题因为是 un-signed int，最高位 = 1 的情况稍微特殊点，把条件改成 != 0 就行了。
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int count = 0;
for(int i = 0; i < 32; i++){
if((n & (1 << i)) != 0) count ++;
}
return count;
}
}
另一种做法是这样，会每次移除最末尾的 siginificant digit，直到 n = 0 为止。
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int count = 0;
while(n!=0){
n-=n&(-n);
count++;
}
return count;
}
}
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
此题重点和难点在于：Do it like a Boss.
- 12 :..............0000001100
- -12 :............11111110100
- 12 & -12:.....0000000100
n - (n & -n) 效果为减去 n 的二进制表示中最右边为 1 的 bit
由于结果肯定比 n 小，bit 数又一定只比 n 多一个，就可以迭代求解了~
Fenwick Tree 万岁~
public class Solution {
public int[] countBits(int num) {
int[] dp = new int[num+1];
for(int i=1;i<=num;i++)
dp[i] = dp[i-(i&-i)]+1;
return dp;
}
}
动态规划, 简单画几个数字就明白, f[i]取决于f[i/2]和i自己的奇偶性
f[i] = f[i / 2] + i % 2.
public class Solution {
public int[] countBits(int num) {
int[] dp = new int[num+1];
for(int i=1;i<=num;i++)
dp[i] = dp[i/2]+i%2;
return dp;
}
}