位运算的技巧(有拓展的技巧)

网络上有一篇位运算的文章,感觉有点新意,因此特意整理一下,转载发表。
最基本的运算如下:
这个我想学过计算机基础都知道,这里好像是使用C语言的。
& - bitwise and
| - bitwise or
^ - bitwise xor
~ - bitwise not
<< - bitwise shift left
>> - bitwise shift right
1、检查整数是偶数还是奇数。

if ((x & 1) == 0)
{
x is even
}
else
{
x is odd
}

2、测试是否设置了 n-th 位。

if (x & (1<<n))
{
n-th bit is set
}
else
{
n-th bit is not set
}

3、设置 第n 位。

y = x | (1<<n)

4、取消第 n 位。

y = x & ~(1<<n)

5、取反第 n 位。

y = x ^ (1<<n)

以上5个很简单,也很实用。在嵌入式中经常会用到的。

6. Turn off the rightmost 1-bit.

y = x & (x-1)

举例说明:
01010111 (x)
& 01010110 (x-1)
--------
01010110
把最右边的1清零

01011000 (x)
& 01010111 (x-1)
--------
01010000

10000000 (x = -128)
& 01111111 (x-1 = 127 (with overflow))
--------
00000000

11111111 (x = all bits 1)
& 11111110 (x-1)
--------
11111110

00000000 (x = no rightmost 1-bits)
& 11111111 (x-1)
--------
00000000

有没有发现,他其实是把这个字节中,最后一个为“1”的bit清零

7. Isolate the rightmost 1-bit.

y = x & (-x)

举例说明:
10111100 (x)
& 01000100 (-x)
--------
00000100
计算得到bit2位的1为最右边的1

01110000 (x)
& 10010000 (-x)
--------
00010000

00000001 (x)
& 11111111 (-x)
--------
00000001

10000000 (x = -128)
& 10000000 (-x = -128)
--------
10000000

11111111 (x = all bits one)
& 00000001 (-x)
--------
00000001

00000000 (x = all bits 0, no rightmost 1-bit)
& 00000000 (-x)
--------
00000000

有没有发现,他其实是得到这个字节中,最后一个为“1”的bit,新的结果中,其实位都是零。

8. Right propagate the rightmost 1-bit.

y = x | (x-1)

举例说明
10111100 (x)
| 10111011 (x-1)
--------
10111111
把字节的最右边的1的右边0都设置为1

01110111 (x)
| 01110110 (x-1)
--------
01110111

00000001 (x)
| 00000000 (x-1)
--------
00000001

10000000 (x = -128)
| 01111111 (x-1 = 127)
--------
11111111

11111111 (x = -1)
| 11111110 (x-1 = -2)
--------
11111111

00000000 (x)
| 11111111 (x-1)
--------
11111111

有没有发现,他其实扩充右边的位为“1”,如果右边的位是0,则把这些位设置为1。

9. Isolate the rightmost 0-bit.

y = ~x & (x+1)
举例说明:
10111100 (x)
--------
01000011 (~x)
& 10111101 (x+1)
--------
00000001
说明最右边的0在第0bit

01110111 (x)
--------
10001000 (~x)
& 01111000 (x+1)
--------
00001000

00000001 (x)
--------
11111110 (~x)
& 00000010 (x+1)
--------
00000010

10000000 (x = -128)
--------
01111111 (~x)
& 10000001 (x+1)
--------
00000001

11111111 (x = no rightmost 0-bit)
--------
00000000 (~x)
& 00000000 (x+1)
--------
00000000

00000000 (x)
--------
11111111 (~x)
& 00000001 (x+1)
--------
00000001
有没有发现,这个计算公式是计算出这个字节中的最右边的位为0的位置。

10. Turn on the rightmost 0-bit.

y = x | (x+1)
举例说明:
10111100 (x)
| 10111101 (x+1)
--------
10111101

01110111 (x)
| 01111000 (x+1)
--------
01111111

00000001 (x)
| 00000010 (x+1)
--------
00000011

10000000 (x = -128)
| 10000001 (x+1)
--------
10000001

11111111 (x = no rightmost 0-bit)
| 00000000 (x+1)
--------
11111111

00000000 (x)
| 00000001 (x+1)
--------
00000001
把字节的最右边的0置为1
以上的6-10的5个技巧,说实话,在实际的项目中使用的很少,但是可以拓展一下位运算的方法,特此记录下。

上一篇:7-1 统计非负整数二进制展开中数位1的总数


下一篇:GDB调试之段信息