位运算的奇技淫巧 (2)

再将奇数位右移一位,偶数位左移一位,此时将两个数据相或即可以达到奇偶位上数据交换的效果:

原数: 10000110 11011000 奇数位右移一位: 0 10000010 1000100 偶数位左移一位:0000100 01010000 0 两数相或得到: 01001001 11100100

上面的方法用位操作可以表示为:

取a的奇数位并用 0 进行填充可以表示为:a & 0xAAAA

取a的偶数为并用 0 进行填充可以表示为:a & 0x5555 因此,上面的第一步可以表示为:
a = ((a & 0xAAAA) >> 1) | ((a & 0x5555) << 1)
同理,可以得到其第二、三和四步为:
a = ((a & 0xCCCC) >> 2) | ((a & 0x3333) << 2)
a = ((a & 0xF0F0) >> 4) | ((a & 0x0F0F) << 4)
a = ((a & 0xFF00) >> 8) | ((a & 0x00FF) << 8)
因此整个操作为:

unsigned short a = 34520; a = ((a & 0xAAAA) >> 1) | ((a & 0x5555) << 1); a = ((a & 0xCCCC) >> 2) | ((a & 0x3333) << 2); a = ((a & 0xF0F0) >> 4) | ((a & 0x0F0F) << 4); a = ((a & 0xFF00) >> 8) | ((a & 0x00FF) << 8);

位操作统计二进制中 1 的个数

统计二进制1的个数可以分别获取每个二进制位数,然后再统计其1的个数,此方法效率比较低。这里介绍另外一种高效的方法,同样以 34520 为例,我们计算其 a &= (a-1)的结果:

第一次:计算前:1000 0110 1101 1000 计算后:1000 0110 1101 0000

第二次:计算前:1000 0110 1101 0000 计算后:1000 0110 1100 0000

第二次:计算前:1000 0110 1100 0000 计算后:1000 0110 1000 0000 我们发现,没计算一次二进制中就少了一个 1,则我们可以通过下面方法去统计:

count = 0 while(a){ a = a & (a - 1); count++; } 找出没有重复的数

给你一组整型数据,这些数据中,其中有一个数只出现了一次,其他的数都出现了两次,让你来找出一个数 。

这道题可能很多人会用一个哈希表来存储,每次存储的时候,记录 某个数出现的次数,最后再遍历哈希表,看看哪个数只出现了一次。这种方法的时间复杂度为 O(n),空间复杂度也为 O(n)了。

然而我想告诉你的是,采用位运算来做,绝对高逼格!

我们刚才说过,两个相同的数异或的结果是 0,一个数和 0 异或的结果是它本身,所以我们把这一组整型全部异或一下,例如这组数据是:1, 2, 3, 4, 5, 1, 2, 3, 4。其中 5 只出现了一次,其他都出现了两次,把他们全部异或一下,结果如下:

由于异或支持交换律和结合律,所以:

1^ 2^ 3^ 4^ 5^ 1^ 2^ 3^4 = (1^ 1)^(2 ^ 2)^ (3^ 3)^ (4^ 4)^5= 00005 = 5。

也就是说,那些出现了两次的数异或之后会变成0,那个出现一次的数,和 0 异或之后就等于它本身。就问这个解法牛不牛逼?所以代码如下

m的n次方

如果让你求解 m 的 n 次方,并且不能使用系统自带的 pow 函数,你会怎么做呢?这还不简单,连续让 n 个 m 相乘就行了,代码如下:

int pow(int n){ int tmp = 1; for(int i = 1; i <= n; i++) { tmp = tmp * m; } return tmp; }

不过你要是这样做的话,我只能呵呵,时间复杂度为 O(n) 了,怕是小学生都会!如果让你用位运算来做,你会怎么做呢?

我举个例子吧,例如 n = 13,则 n 的二进制表示为 1101, 那么 m 的 13 次方可以拆解为:

\(m^{1101} = m^{0001} * m^{0100} * m^{1000}\)

我们可以通过 & 1和 >>1 来逐位读取 1101,为1时将该位代表的乘数累乘到最终结果。直接看代码吧,反而容易理解:

int pow(int n){ int sum = 1; int tmp = m; while(n != 0){ if(n & 1 == 1){ sum *= tmp; } tmp *= tmp; n = n >> 1; } return sum; }

时间复杂度近为 \(O(logn)\),而且看起来很牛逼。

这里说一下,位运算很多情况下都是很二进制扯上关系的,所以我们要判断是否是否位运算,很多情况下都会把他们拆分成二进制,然后观察特性,或者就是利用与,或,异或的特性来观察,总之,我觉得多看一些例子,加上自己多动手,就比较容易上手了。所以呢,继续往下看,注意,先别看答案,先看看自己会不会做。

找出不大于N的最大的2的幂指数

传统的做法就是让 1 不断着乘以 2,代码如下:

int findN(int N){ int sum = 1; while(true){ if(sum * 2 > N){ return sum; } sum = sum * 2; } }

这样做的话,时间复杂度是 $O(logn)¥,那如果改成位运算,该怎么做呢?我刚才说了,如果要弄成位运算的方式,很多时候我们把某个数拆成二进制,然后看看有哪些发现。这里我举个例子吧。

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zwpfyx.html