Heim  >  Artikel  >  Datenbank  >  (译)你必须知道的位运算技巧 Low Level Bit Hacks You Absolutel

(译)你必须知道的位运算技巧 Low Level Bit Hacks You Absolutel

WBOY
WBOYOriginal
2016-06-07 14:59:341730Durchsuche

from HackerMonthly-issue15 By Peteris Krumins 我准备写一篇关于嵌入系统开发者所熟知的有关位运算技巧的文章. 位运算技巧可以巧妙有效的操作整数.在如计算一个整数中包含多少个1之类的操作时,这些技巧可以只用几个位操作符搞定. 假定你已具备2的补码和位

from HackerMonthly-issue15
By Peteris Krumins

 

我准备写一篇关于嵌入系统开发者所熟知的有关位运算技巧的文章. 位运算技巧可以巧妙有效的操作整数.在如计算一个整数中包含多少个1之类的操作时,这些技巧可以只用几个位操作符搞定.

假定你已具备2的补码和位运算操作的知识.

下面的文章将使用以下简写:

& -  and
| -  or
^ -  xor
~ -  not
>> -  右移

本文里的整数指 8bit (虽然也适用于任意长度的有符号整数) 的有符号整数,我们用 x 表示,结果用 y 表示, x 的每个bit 有 b7,b6,b5,b4,b3,b2,b1 和 b0,符号位 b7 为最高位,b0为最低位.

我将从最常用的技巧开始,然后渐渐趋于更难的技巧.并使用示例代码解释每个技巧的工作原理.

 

位运算技巧1: 判断一个整数奇偶

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

我相信所有人都见过这个,它的原理是判断最后一个bit b0如果是1的话就是奇数. 用1 and x 将消除除b0以外的位,那么如果结果为0 x即为偶数,否则x 为奇数.

来看些例子,比如43,是一个奇数,用二制表示即 00101011. 它的最后一位b0 是1,将它和1 作AND 操作:

00101011
& 00000001
--------
00000001

 

可以看到 AND 抹掉了b1-b7,但b0依然保持原样,运算的最终结果是1,告诉我们它是他奇数.

那么我们再看看-43,提醒一下,在2的补码表示方法,对一个正整数取负的步骤是反转每一位然后加1,所以-43的二进制表示为11010101.再次强调一下最后一个bit是1,所以是奇数.(如果我们用1的补码就不正确了)

再看一个偶数98,其二进制表示是 1100010

01100010
& 00000001
--------
00000000

AND的结果是0,意味着98的b0是0,指定的整数为偶数.

-98二进制表示为 10011110. 同样b0 为0,AND后结果为0

 

位运算技巧2: 判断第n位是否置1.

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

在前面的技巧中,我们看到(x&1)测试第一个位是否置1.这个技巧更进一步可以判断第n位是否置1.方法是向左移n位再求AND,这会抹掉除第n位的其他位.

下面演示了左移的效果.

1 00000001 (等同于 11111111

 

好,我们将左移n位后再和x AND,就快速抹掉x除了第n位的其他位.如果AND后结果为0,那么那个位一定是0,否则就是置1的

看几个例子.

122的第三位是否有值,下面这个操作会找到答案:

122 & (1

122的二进制表示01111010,1

01111010
& 00001000
--------
00001000

 

可以看到最终结果不是0,所以122的第三位是置1

那么-33的第5位是否置1呢?

11011111 (-33 in binary)
& 00100000 (1--------
00000000

结果是0,所以第5位是未置1的.

 

 

技巧3 将第n位置1

y = x | (1

这个技巧结合了1

假设一个数 120,我们想将它的第2位置1.

01111000 (120 in binary)
| 00000100 (1--------
01111100

再试试将-120第6位置1

10001000 (-120 in binary)
| 01000000 (1--------
11001000

 

技巧4 : 将第n位置0

y = x & ~(1

这个玩法最核心的部分是~(1

~1 11111110 (same as ~(1~(1~(1~(1~(1~(1~(1~(1

 

不管第n位是0还是1,x和这些数AND 的效果都是将第n位置0.

看下面的例子,将127的第4位置0

01111111 (127 in binary)
& 11101111 (~(1--------
01101111

 

技巧5: 反转第n位

y = x ^ (1

这个玩法同样使用将第n位置1的技巧,但是用的是XOR操作,一个位和另一个位进行XOR,如果它们相同那么结果是0,否则为1.那么怎么切换第n位了? 如果第n位是1,和1 XOR后,1变成0,反之0和1 XOR 结果为1.所以位反转了.

下面这个例子演示了怎么将01110101 第5位反转:

01110101
^ 00100000
--------
01010101

如果第5位已经是0了呢?

01010101
^ 00100000
--------
01110101

看出端倪了没?XOR两次又还原了. 巧妙的XOR常被用来计算RAID阵列的奇偶校验和简单的加密函数中和其他方面

 

技巧6: 将最右边的1置0

y = x & (x-1)

终于来点有趣的了! 说实在的,前5个玩法有点无聊.

这个玩法将最后一个1置0,例如 00101010,变为00101000. 或者00010000,变为0.

例:

01010111 (x)
& 01010110 (x-1)
--------
01010110


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

 

10000000 (x = -128)
& 01111111 (x-1 = 127 (溢出))
--------
00000000


11111111 (x = 都是1 1)
& 11111110 (x-1)
--------
11111110


00000000 (x 没有是1的位)
& 11111111 (x-1)
--------
00000000

那它的原理是呢?

如果你稍加思索,你就会发现有下面两种情况:

1. 位列中有1. 减1会将低位变为1并将最后一个1的位变0.这步再和原来的值AND屏蔽了从最后一个1的后面部分.

2.位列中没有1都是0.这是减去1将溢出所有位都变成1. 和都是0的位列AND 还是0.

 

技巧7 拨离最右边的1

y = x & (-x)

这个玩法找到最右边的一个1并将其他位置0,例如01010100,转换后为00000100.

例:

10111100 (x)
& 01000100 (-x)
--------
00000100


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
& 00000000 (-x)
--------
00000000

 

这个技巧归功于2的补码,在2的补码中-x和~x+1.

 

技巧8: 将右边第一个1后的位全置1

y = x | (x-1)

这个最好结合例子来理解. 将01010000 变成 01011111.从右边第一个1开始,后面的0全变成了1.

这不是一个完美的技巧,当x=0时,结果都是1

例:

10111100 (x)
| 10111011 (x-1)
--------
10111111


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

 

技巧9: 拨离最右边的第一个0

这个技巧和第7个的相反.找到最右的0,将它置1并将其他位置0. 例如 将10101011,转换成00000100.

更多的例子:

--------
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

 

技巧10: 将最右边0位置1

y = x | (x+1)

将最右边的0置1.如将10100011 转换为 10100111.

 

更多的例子:

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

 

其他内容:

如果你对其他位操作技巧感兴趣,下面有一些Python,C的代码方便打印8位的符号整数

Python 代码:

<span>def</span> int_to_bin(num, bits=8):
  r = ''
  while bits:
    r = ('1' <span>if</span> num&1 <span>else</span> '0') + r
    bits = bits - 1
    num = num >> 1
<span>print</span> r


C代码:

<span>void</span> int_to_bin(<span>int</span> num) {
  <span>char</span> str[9] = {0};
  <span>int</span> i;
  <span>for</span> (i=7; i>=0; i--) {
    str[i] = (num&1)?'1':'0';
    num >>= 1;
  }
  <span>printf</span>("<span>%s\n</span>", str);
}
Stellungnahme:
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Vorheriger Artikel:SQL Server中的行列倒置技巧Nächster Artikel:数据库总结