这是之前准备面试问题的笔记，跟大家分享。 主要是在讨论用bitwise parallel的技巧去解一些问题，下面这些问题 可以用类似的技巧去解，或许也可以用类似的技巧解更多问题。当然这 些解法不是问题的唯一解法，也不一定是最快速的解法，像是用查表法 这些问题都可以得到解答。我只是觉得这群问题都可以用类似的方法解 决很有趣而已。 如果有人知道其他问题也可以用类似的技巧解，请告诉我，我会很感激的。 假设给定一个32bit无号整数，如果以byte为单位切成四份，求这四份的数字总合。 范例 0x09ABCDEF -> 0x09 + 0xAB + 0xCD + 0xEF 直觉的方法就是 x & 0xFF + (x&0xFF00 >> 8) + (x&0xFF0000 >> 16) + (x&0xFF000000 >> 24) 第二种是第一种的变形，可以少一个加法运算和shift运算 x = x & 0x00FF00FF + (x & 0xFF00FF00 >> 8) x = ((x & 0xFFFF0000) >> 16) + x & 0x0000FFFF 原理就是把原本的第一个和第三个加法同时间一起做而已，相当於把32bit 的加法器，当成两个8bit加法器来用。 用Parallel的技巧可以让速度加快，理论上有很多运算需要O(n)次 的运算才能完成（此地的n为整数的bit数）。不过实际上如果整数 的bit数固定，而且CPU可以支援位元运算的话，许多动作只要O(lgn) 的时间就可以完成了。 像是可以用来计算parity上面 （parity就是把32个bit xor起来，原本需要31次的xor） x ^= x >> 16; x ^= x >> 8; x ^= x >> 4; x ^= x >> 2; x = (x ^ (x >> 1)) & 1; 同样的技巧，也可以用来做把整数中的bit反转的动作 （简单的实作需要16次的交换） x = ((x >> 1) & 0x55555555) | ((x & 0x55555555) << 1); x = ((x >> 2) & 0x33333333) | ((x & 0x33333333) << 2); x = ((x >> 4) & 0x0F0F0F0F) | ((x & 0x0F0F0F0F) << 4); x = ((x >> 8) & 0x00FF00FF) | ((x & 0x00FF00FF) << 8); x = ( x >> 16 ) | ( x << 16); 最广为人知的是做bit counting，计算整数中有几个位元为1。 （暴力法需要判断32次） x = ((x >> 1) & 0x55555555) + (x & 0x55555555); x = ((x >> 2) & 0x33333333) + (x & 0x33333333); x = ((x >> 4) & 0x0F0F0F0F) + (x & 0x0F0F0F0F); x = ((x >> 8) & 0x00FF00FF) + (x & 0x00FF00FF); x = ((x >> 16) & 0x0000FFFF) + (x & 0x0000FFFF); 一个比较少人知道的是做bit shuffle，假设32个bit是 b1 b2 b3 .... b32，做shuffle是要把位元转成 b1 b17 b2 b18 ... b16 b32 就好像扑克牌的完美洗牌一样 x = (x & 0xFF0000FF) | ((x & 0x00FF0000) >> 8) | ((x & 0x0000FF00) << 8); x = (x & 0xF00FF00F) | ((x & 0x0F000F00) >> 4) | ((x & 0x00F000F0) << 4); x = (x & 0xC3C3C3C3) | ((x & 0x30303030) >> 2) | ((x & 0x0C0C0C0C) << 2); x = (x & 0x99999999) | ((x & 0x44444444) >> 1) | ((x & 0x22222222) << 1); --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.119.162.51