无苦邪
2022/12/12阅读:22主题:橙心
小白学算法(5)之位运算
开启掘金成长之旅!这是我参与「掘金日新计划 · 12 月更文挑战」的第9天,点击查看活动详情[1]
位运算
1.十进制与二进制的转换
位运算是针对于2进制而言,所以进行运算时首先要将数字进行转换2进制,这里介绍8421法
十进制 二进制
1 0001
2 0010
4 0100
8 1000
16 10000
.....
这就是所谓8421法,这样可以很快进行十进制和二进制的转换
如5=4+1
0100+0001=0101
2.模板
(1)求n的第k位数字: n >> k & 1
那么我们这里就要先理解一下>>和<<运算符了
1)<<左移运算符 5<<2 左移两位 0101<<2-->0101 00=20 将一个运算对象的各二进制位全部左移若干位(左边的二进制丢弃,右边补0) 对于一个正数(无符号数)而言,左移1位就相当于*2,可以参考上面的8421法就可得知
2)>>右移运算符 5>>2 右移两位 0101>>2-->0001|(01)=1 正负数右移就不一样了 将一个运算对象的各二进制位全部右移若干位,正数左补0,负数左补1. 对于一个正数(无符号数)而言,左移1位就相当于/2,可以参考上面的8421法就可得知
3)& 按位与 这里要与&&进行区分,&&是逻辑运算符 所得到的结果真/假,只适用于编程语言中 因为不同语言的返回值不同,比如Java返回是true/false,C返回1/0 1&&0=假 1&&1=真,0&&0=假, 而&是按位运算符 使用范围较广,算法 即全1为1,其他全为0 1&1=1,1&0=0,0&0=0
解释模板: 理解了上面三种运算符,就可以很好解释该模板 n>>k:求第几位就左移几位,注意这里的第几位是从右向左算,并且0开始。使得所求位成为最后一位 &1:1转换为二进制即 00000000000000001,前面全0,只有最后一位为1,所以只会求得最后一位
(2).返回n的最后一位1:lowbit(n) = n & -n
&是二进制的运算
所以这里需要理解一个概念
-n的原码=n的原码取反+1(~n+1), ~就是取反的意思
5(0101)
~5(1010)
~5+1(1011)
所以5&(-5)=(0101)&(1011)=(0001) 得到的最后一位1为0001 ,第二个1是 0100=4
为什么这样可以得到最后一位1呢,我由图解释

我们可以得到最后一位1
之后的所有位都为0,取反
后最后一位1变成了0,后面所有的0都变成了1,此时再+1
,后面的1都会形成进位到最后一位1所取反的0
(鼠标画图太难了,以后用平板画🥲)
(3)实际应用
给定一个长度为 nn 的数列,请你求出数列中每个数的二进制表示中 1的个数。
通过上面模板我们可以求出最后一位1的数,我们可以去掉最后一位1的数,然后使得倒数第二位1的成为最后一位
#include<iostream>
using namespace std;
const int MAX=1e5+10;
int A[MAX];
int lowbit(int x)
{
return x&(-x); -x=~x+1 为x的补码
}
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
{
int res=0;
cin>>A[i];
//判断是否还有1
while(lowbit(A[i]!=0))
{
//减去最后一位1的数,下一次判断就是倒数第二位的了
A[i]-=lowbit(A[i]);res++;
}
cout<<res<<" ";
}
return 0;
}
位运算是针对于二进制而言,所以多于很多还不了解二进制运算的帅读者有点困难,但理解原理便变得通达了,毕竟二进制除了位数较多外,它的值只有1/0
感谢观看。😁
参考资料
https://juejin.cn/post/7167294154827890702: https://juejin.cn/post/7167294154827890702
作者介绍