规定:
二进制数从下标0
开始记数
如:
第k位 9 8 7 6 5 4 3 2 1 0
1 0 1 0 0 0 0 1 1 1
因此二进制数1010000111
的第6
位是0
求10进制数n的二进制第k位是0还是1
原理:n>>k&1
1:向右位移k位
2:与1进行与运算
如:
647的二进制数1010000111向右移动6位得
第k位 9 8 7 6 5 4 3 2 1 0
1 0 1 0 0 0 0 1 1 1
向右移动6位后得到
第k位 9 8 7 6 5 4 3 2 1 0
1 0 1 0
此时第0位即为所求数,取出第0位即可
1010 & 1 = 0
lowbit(n)输出n的二进制数的最后一位1的位置到第0位
如:
lowbit(10944) = 64
1 0 1 0 1 0 1 1 0 0 0 0 0 0 = 10944
->
1 0 0 0 0 0 0 = 64
n的负数的二进制表示为其补码(补码是原码取反后加1)
-99 = ~99 + 1
原理:n与-n进行与运算
lowbit(n) = n & -n
若n的二进制数串满足以下形式:
n = 1 0 1 0 1 ... 0 1 0 0 0 ... 0 0 0
^
~n = 0 1 0 1 0 ... 1 0 1 1 1 ... 1 1 1
^
-n = ~n + 1 = 0 1 0 1 0 ... 1 1 0 0 0 ... 0 0 0
^
n & -n = 0 0 0 0 0 ... 0 1 0 0 0 ... 0 0 0
^
即 1 0 0 0 ... 0 0 0
统计n的二进制数中1的个数:
int cnt=0;
while(n){
n-=lowbit(n);
cnt++;
}
cout<<cnt;
n自乘2
n<<=1
判断奇偶
特点:
奇数的二进制数末尾为1,偶数为0
if(x&1) x为奇数
else x为偶数