Liuxboy

while(true) coding

Bit Twiddling Hacks

2015-04-27 | Comments

By Sean Eron Anderson

seander@cs.stanford.edu

向大神致敬，请收下我的膝盖，先让跪会儿，然后再站起，擦干眼泪学习!

Individually, the code snippets here are in the public domain (unless otherwise noted) — feel free to use them however you please. 特别地声明，这些代码片段都是公开的（特别注明除外）——只要你需要，你可自由地使用它们。 The aggregate collection and descriptions are ? 1997-2005 Sean Eron Anderson. The code and descriptions are distributed in the hope that they will be useful, 这份文档的收集和说明由?1997-2005 Sean Eron Anderson完成. 虽然发布这些代码和说明是希望朝一日能发挥它的作用, but WITHOUT ANY WARRANTY and without even the implied warranty of merchantability or fitness for a particular purpose. 但是这并不保证，也不暗自保证其用于某一特殊目时的适用性和正确性. As of May 5, 2005, all the code has been tested thoroughly. Thousands of people have read it. Moreover, Professor Randal Bryant, 截至2005年5月5日，这些代码都经过了充分的测试。成千上万的人都读过这些代码. 甚至卡内基.梅隆大学计算机系主任，Randal Bryant教授, 还亲自将其在它的“欧几里德 ”代码验证系统上几乎全部测试过. the Dean of Computer Science at Carnegie Mellon University, has personally tested almost everything with his Uclid code verification system. What he hasn’t tested, I have checked against all possible inputs on a 32-bit machine. To the first person to inform me of a legitimate bug in the code, 那些他还没有测试到的，我也已经检查了32位机器上对所有可能的输入. 第一个向我报告一个有效bug的人，我将向其支付10美元(用支票或者PayPal都行). 如转交慈善机构的话，我将支付20美元. I’ll pay a bounty of US$10 (by check or Paypal). If directed to a charity, I’ll pay US$20.

目录

  • 关于计数操作方法
  • 推算一个整数的符号
  • 探测两个整数具有相反的符号
  • 一行代码计算整数的绝对值
  • 一行代码得出两个整数的最大值或最小值
  • 确定一个整数是2的幂
  • 符号扩展
    • Sign extending from a constant bit-width
    • 符号扩展自常量的bit位宽 Sign extending from a variable bit-width
    • 符号扩展自变量的bit位宽 Sign extending from a variable bit-width in 3 operations
    • 符号扩展自变量的bit位宽的三步操作
  • Conditionally set or clear bits without branching
  • 无分支，有条件地设置或清空二进制数
  • Conditionally negate a value without branching
  • 无分支，有条件取某个数的相反数
  • Merge bits from two values according to a mask
  • 将两个数通过掩码按位合并
  • Counting bits set
  • 计算二进制数集合
    • Counting bits set, naive way
    • 计算二进制集合(朴素办法)
    • Counting bits set by lookup table
    • 计算二进制集合，通过查找表
    • Counting bits set, Brian Kernighan’s way
    • 计算二进制集合，通过布莱恩·柯林汉方法
    • Counting bits set in 14, 24, or 32-bit words using 64-bit instructions
    • 通过64位字长的指令，计算14位，24位或32位字长的二进制集合
    • Counting bits set, in parallel
    • 计算二进制集合，采用并行方式
    • Count bits set (rank) from the most-significant bit upto a given position
    • 计算二进制集合（等级），通过某个给定位置上的明显标志位
    • Select the bit position (from the most-significant bit) with the given count (rank)
    • 选出给定计数（等级）时某个明显标志位上的二进制数
  • Computing parity (1 if an odd number of bits set, 0 otherwise)
  • 计算奇偶性（在二进制集合中，1是奇数，0则是偶数）
    • Compute parity of a word the naive way
    • 通过朴素方法判断一个字的奇偶性
    • Compute parity by lookup table
    • 通过查找表判断奇偶性
    • Compute parity of a byte using 64-bit multiply and modulus division
    • 用64位相乘和除模判断奇偶性
    • Compute parity of word with a multiply
    • 通过乘法判断一个字的奇偶性
    • Compute parity in parallel
    • 并行方式判断奇偶性
  • Swapping Values
    • Swapping values with subtraction and addition
    • 使用加法或减法交换两数
    • Swapping values with XOR
    • 使用异或交换两数
    • Swapping individual bits with XOR
    • 使用异或交换单个二进制数
  • Reversing bit sequences
  • 转换二进制序列
    • Reverse bits the obvious way
    • 通过常规方法转换二进制数
    • Reverse bits in word by lookup table
    • 通过查找表转换一个字长的二进制数
    • Reverse the bits in a byte with 3 operations (64-bit multiply and modulus division)
    • 通过3步操作（64位乘法和除模）
    • Reverse the bits in a byte with 4 operations (64-bit multiply, no division)
    • 通过4步操作（64位乘法, 不要除数）
    • Reverse the bits in a byte with 7 operations (no 64-bit, only 32)\

Reverse an N-bit quantity in parallel with 5 * lg(N) operations Modulus division (aka computing remainders) Computing modulus division by 1 << s without a division operation (obvious) Computing modulus division by (1 << s) - 1 without a division operation Computing modulus division by (1 << s) - 1 in parallel without a division operation Finding integer log base 2 of an integer (aka the position of the highest bit set) Find the log base 2 of an integer with the MSB N set in O(N) operations (the obvious way) Find the integer log base 2 of an integer with an 64-bit IEEE float Find the log base 2 of an integer with a lookup table Find the log base 2 of an N-bit integer in O(lg(N)) operations Find the log base 2 of an N-bit integer in O(lg(N)) operations with multiply and lookup Find integer log base 10 of an integer Find integer log base 10 of an integer the obvious way Find integer log base 2 of a 32-bit IEEE float Find integer log base 2 of the pow(2, r)-root of a 32-bit IEEE float (for unsigned integer r) Counting consecutive trailing zero bits (or finding bit indices) Count the consecutive zero bits (trailing) on the right linearly Count the consecutive zero bits (trailing) on the right in parallel Count the consecutive zero bits (trailing) on the right by binary search Count the consecutive zero bits (trailing) on the right by casting to a float Count the consecutive zero bits (trailing) on the right with modulus division and lookup Count the consecutive zero bits (trailing) on the right with multiply and lookup Round up to the next highest power of 2 by float casting Round up to the next highest power of 2 Interleaving bits (aka computing Morton Numbers) Interleave bits the obvious way Interleave bits by table lookup Interleave bits with 64-bit multiply Interleave bits by Binary Magic Numbers Testing for ranges of bytes in a word (and counting occurances found) Determine if a word has a zero byte Determine if a word has a byte equal to n Determine if a word has byte less than n Determine if a word has a byte greater than n Determine if a word has a byte between m and n Compute the lexicographically next bit permutation