位运算的方法,小结

文章来源未知----再次声明为转载...

本文是针对使用位运算来实现一些方法,我们都知道位运算的代价比其他符号运算都低,所以当一个方法只使用位运算且运算次数与其他不纯使用位运算的方法相等时,所用的时间肯定是最短的,甚至即使运算次数比其他 方法多,也是有可能花的时间短的。

这里计算算法的衡量标准是位运算的运算此时,任何C的位运算符当作一次运算,不写到RAM的中间赋值不算运算,当然这里假设每次运算代价都是近似相同的机器指令和CPU时间。当然实际上不是所有的运算的时间都是相同的。我们知道有很多东西影响系统运行一段代码所花的时间长短,比如缓存的大小,内存的带宽,机器指令集等等。当然制定一个衡量标准来判断一个方法是否比另外一个方法快,这样是最好的解决方案, 这里的衡量标准就是运算的次数。

计算一个整数的符号(是+或者-)

int v;      // 待检测的数

int sign;   // 符号结果,0表示正数或者0,-1表示负数

// CHAR_BIT 是一个字节的位数 (通常是8).

sign = -(v < 0);  // if v < 0 then -1, else 0.

// 或者避免使用CPU判断,因为那会增加cost:

sign = -(int)((unsigned int)((int)v) >> (sizeof(int) * CHAR_BIT - 1));

// 或者更少的运算:

sign = v >> (sizeof(int) * CHAR_BIT - 1);

更多的人喜欢用-1表示复数,+1表示正数或者0,那么我们可以用: 

sign = +1 | (v >> (sizeof(int) * CHAR_BIT - 1));  // if v < 0 then -1, else +1

另外用-1,0,+1分别表示负数,0,正数的方法有: 

sign = (v != 0) | -(int)((unsigned int)((int)v) >> (sizeof(int) * CHAR_BIT - 1));

//或者更快一点的方法,但移植性差:

sign = (v != 0) | (v >> (sizeof(int) * CHAR_BIT - 1));  // -1, 0, or +1

//或者更简洁,移植性高和速度快的方法是:

sign = (v > 0) - (v < 0); // -1, 0, or +1

如果你想知道一个数是不是非负数,结果是1(非负)否则0(负数),那么可以用:

sign = 1 ^ ((unsigned int)v >> (sizeof(int) * CHAR_BIT - 1)); // if v < 0 then 0, else 1


判断两个数是否有相反的符号

int x, y;               // 待检测的两个数

bool f = ((x ^ y) < 0); // true 表示 x和y有相反的符号, false表示x,y有相同的符号。


计算一个整数的绝对值(无判断分支)

int v;           // 待计算的值

unsigned int r;  // 结果

int const mask = v >> sizeof(int) * CHAR_BIT - 1;

r = (v + mask) ^ mask;

//或者

r = (v ^ mask) - mask;

有些cpu没有计算绝对值的指令,或者编译器不会使用机器的求绝对值的指令,使用分支判断的代价是相对比较高的,所以使用上面的方法会比用分支的判读的方法快, 例如下面是用判断分支r = (v < 0) ? -(unsigned)v : v

即使这个方法运算符的次数与上面的是一样的,这个的速度还是慢。


计算两个数中的最小或者最大值(无判断分支)

int x;  //需要取最小(大)值的两个数

int y;  

int r;  //比较结果

r = y ^ ((x ^ y) & -(x < y)); // min(x, y)

在某些机器,有判断分支的的指令花的时间会很长而且没有条件移动指令,所以上面这个方法会比下面这个方法快, r = (x < y) ? x : y.

要得到最大值:

r = x ^ ((x ^ y) & -(x < y)); // max(x, y)

假如你知道INT_MIN <= x-y <= INT_MAX 而不会溢出,那么你可以用下面的方法会更快。

r = y + ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1))); // min(x, y)

r = x - ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1))); // max(x, y)


判断一个整数是否是2的次方

unsigned int v; //待检测的数

bool f;         // 结果

f = (v & (v - 1)) == 0;

这里要注意,0不能正确识别为2的次方,为了克服这个,可以用下面的方法

f = v && !(v & (v - 1));


将一个固定位数的整数进行扩展更大的位数的整数

小整数向大整数的转换一般是cpu自动转换的,如将char转成int. 下面的例子是将5位宽的int转换成一个32位的int:

int x; // 待转换的数

int r; // 结果

struct {signed int x:5;} s;

r = s.x = x;

下面这个是用C++的模板方法来实现.

template <typename T, unsigned B>

inline T signextend(const T x)

{

  struct {T x:B;} s;

  return s.x = x;

}

int r = signextend<signed int,5>(x); 


设置或清除位(无判断分支)

bool f;         // 条件flag

unsigned int m; // 位掩码

unsigned int w; // 需要被修改的数:  if (f) w |= m; else w &= ~m;

w ^= (-f ^ w) & m;

// 或者:

w = (w & ~m) | (-f & m);

因为有些cpu的系统架构使用if分支判断时会使用多次操作。例如:非正式的测试中AMD Athlon XP 2100+显示出使用上述方法比用if快5-10%, Intel Core 2 Duo 则是快16%。


根据条件取某数的相反数(无判断分支)

bool fDontNegate;  //条件flag.

int v;             // 输入的数.

int r;             // result = fDontNegate ? v : -v;

r = (fDontNegate ^ (fDontNegate - 1)) * v;

如果只有flag为真时求v的相反数,可以用下面的方法:

bool fNegate;  // 条件flag.

int v;         // 输入的数.

int r;         // result = fNegate ? -v : v;

r = (v ^ -fNegate) + fNegate;


根据掩码把两个数进行位合并

unsigned int a;    // 将要被合并的数a

unsigned int b;    // 将要被合并的数b

unsigned int mask; // 1 where bits from b should be selected; 0 where from a.

unsigned int r;    // r = (a & ~mask) | (b & mask)

r = a ^ ((a ^ b) & mask);  


计算一个数里位被置1的个数 (比较差的方法)

unsigned int v; // 待检测的数

unsigned int c; // 位被置1的总数

for (c = 0; v; v >>= 1)

{

  c += v & 1;

}

这个方法需要进行32次循环,效率低。


计算一个数里位被置1的个数(查表)

static const unsigned char BitsSetTable256[256] =

{

#define B2(n) n,     n+1,     n+1,     n+2

#define B4(n) B2(n), B2(n+1), B2(n+1), B2(n+2)

#define B6(n) B4(n), B4(n+1), B4(n+1), B4(n+2)

    B6(0), B6(1), B6(1), B6(2)

};

unsigned int v; // 待检测的数

unsigned int c; // 位被置1的总数

// 公式1:

c = BitsSetTable256[v & 0xff] +

    BitsSetTable256[(v >> 8) & 0xff] +

    BitsSetTable256[(v >> 16) & 0xff] +

    BitsSetTable256[v >> 24];

// 公式2:

unsigned char * p = (unsigned char *) &v;

c = BitsSetTable256[p[0]] +

    BitsSetTable256[p[1]] +

    BitsSetTable256[p[2]] +   

    BitsSetTable256[p[3]];

// 也可以用如下方法来构造表:

BitsSetTable256[0] = 0;

for (int i = 0; i < 256; i++)

{

  BitsSetTable256[i] = (i & 1) + BitsSetTable256[i / 2];

}


计算一个数里位被置1的个数(Brian Kernighan's way)

unsigned int v; // 待检测的数

unsigned int c; // 位被置1的总数

for (c = 0; v; c++)

{

  v &= v - 1;

}


计算一个数里位被置1的个数(使用64位机器指令计算14位,24位,32位数的置1的位数)

unsigned int v; // 待检测的数

unsigned int c; // 位被置1的总数

//公式1 计算最大为14位的数:

c = (v * 0x200040008001ULL & 0x111111111111111ULL) % 0xf;

//公式2 计算最大为24位的数:

c =  ((v & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;

c += (((v & 0xfff000) >> 12) * 0x1001001001001ULL & 0x84210842108421ULL)

     % 0x1f;

//公式3 计算最大为32位的数:

c =  ((v & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;

c += (((v & 0xfff000) >> 12) * 0x1001001001001ULL & 0x84210842108421ULL) %

     0x1f;

c += ((v >> 24) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;

公式1只有3次运算,公式2有10次运算,公式3有15次运算。


计算一个数里位被置1的个数(并行的)

unsigned int v; // 待检测的数(32位)

unsigned int c; //位被置1的总数

static const int S[] = {1, 2, 4, 8, 16}; // 参照表1

static const int B[] = {0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF, 0x0000FFFF}; //参照表2

c = v - ((v >> 1) & B[0]);

c = ((c >> S[1]) & B[1]) + (c & B[1]);

c = ((c >> S[2]) + c) & B[2];

c = ((c >> S[3]) + c) & B[3];

c = ((c >> S[4]) + c) & B[4];

B数组的二进制显示为:

B[0] = 0x55555555 = 01010101 01010101 01010101 01010101

B[1] = 0x33333333 = 00110011 00110011 00110011 00110011

B[2] = 0x0F0F0F0F = 00001111 00001111 00001111 00001111

B[3] = 0x00FF00FF = 00000000 11111111 00000000 11111111

B[4] = 0x0000FFFF = 00000000 00000000 11111111 11111111

可以调整S和B来适应更大位数的整数,如果有k位的整数,S和B的长度应该是ceil(lg(k)), c计算的次数对应增加到S和B的长度次数。

对于32位整数,要使用到16 个运算来计算位置1的个数。

计算32位整数的位置1的个数最好的方法是:

v = v - ((v >> 1) & 0x55555555);                   

v = (v & 0x33333333) + ((v >> 2) & 0x33333333);    

c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count

这里只用到12此运算。跟查表的次数相同,但省去了表的空间。

一个最好的泛型的计算整数(最高到128位, T是传入的类型)的位置1的个数最好的方法是:

v = v - ((v >> 1) & (T)~(T)0/3);                          

v = (v & (T)~(T)0/15*3) + ((v >> 2) & (T)~(T)0/15*3);     

v = (v + (v >> 4)) & (T)~(T)0/255*15;                     

c = (T)(v * ((T)~(T)0/255)) >> (sizeof(T) - 1) * CHAR_BIT; // count


计算一个数里位被置1的个数(只计算从某个位开始到头的置1的位数)

  uint64_t v;       //待检测的数

  unsigned int pos; // 开始的位(从右边数)

  uint64_t r;       // 结果

  // 先右移pos的位

  r = v >> (sizeof(v) * CHAR_BIT - pos);

  // 并行的方法求结果

  // r = (r & 0x5555...) + ((r >> 1) & 0x5555...);

  r = r - ((r >> 1) & ~0UL/3);

  // r = (r & 0x3333...) + ((r >> 2) & 0x3333...);

  r = (r & ~0UL/5) + ((r >> 2) & ~0UL/5);

  // r = (r & 0x0f0f...) + ((r >> 4) & 0x0f0f...);

  r = (r + (r >> 4)) & ~0UL/17;

  // r = r % 255;

  r = (r * (~0UL/255)) >> ((sizeof(v) - 1) * CHAR_BIT);


计算奇偶校验位(普通的方法)

unsigned int v;       // 要被计算的数

bool parity = false;  // 结果

while (v)

{

  parity = !parity;

  v = v & (v - 1);

}


计算奇偶校验位(查表方法)

static const bool ParityTable256[256] =

{

#   define P2(n) n, n^1, n^1, n

#   define P4(n) P2(n), P2(n^1), P2(n^1), P2(n)

#   define P6(n) P4(n), P4(n^1), P4(n^1), P4(n)

    P6(0), P6(1), P6(1), P6(0)

};

unsigned char b;  // 待计算校验位的字节

bool parity = ParityTable256[b];  //结果

// 对32位整数的计算:

unsigned int v;

v ^= v >> 16;

v ^= v >> 8;

bool parity = ParityTable256[v & 0xff];

// 另外一种公式:

unsigned char * p = (unsigned char *) &v;

parity = ParityTable256[p[0] ^ p[1] ^ p[2] ^ p[3]];


计算字节奇偶校验位(使用64位的位运算以及*和%运算)

unsigned char b;  // byte value to compute the parity of

bool parity =

  (((b * 0x0101010101010101ULL) & 0x8040201008040201ULL) % 0x1FF) & 1;

The method above takes around 4 operations, but only works on bytes.


计算奇偶校验位(使用位运算以及*运算)  

下面的运算只用了8次运算.

    unsigned int v; // 待计算校验位的32位数

    v ^= v >> 1;

    v ^= v >> 2;

    v = (v & 0x11111111U) * 0x11111111U;

    return (v >> 28) & 1;

对于64位整数也只需要8次运算.

    unsigned long long v; // 64位整数

    v ^= v >> 1;

    v ^= v >> 2;

    v = (v & 0x1111111111111111UL) * 0x1111111111111111UL;

    return (v >> 60) & 1;


计算奇偶校验位(并行的)

unsigned int v;  //待计算校验位的32位数

v ^= v >> 16;

v ^= v >> 8;

v ^= v >> 4;

v &= 0xf;

return (0x6996 >> v) & 1;

上面的方法用了9次运算,对32位数适用。


交换两个变量的值(只使用+,-还有位操作,无多余变量)

#define SWAP(a, b) ((&(a) == &(b)) || /

                    (((a) -= (b)), ((b) += (a)), ((a) = (b) - (a))))

不建议对浮点数使用这个方法,会比XOR的方法慢.


交换两个变量的值(只使用XOR)

#define SWAP(a, b) (((a) ^= (b)), ((b) ^= (a)), ((a) ^= (b)))


交换一个数里独立的位(只使用XOR)  

unsigned int i, j; // 要交换的位的起始位置

unsigned int n;    // 要交换的位数

unsigned int b;    // 被交换的数

unsigned int r;    // 交换独立位之后的结果

unsigned int x = ((b >> i) ^ (b >> j)) & ((1U << n) - 1); // XOR temporary

r = b ^ ((x << i) | (x << j));

例如b = 00101111 (二进制) ,我们要交换从起始位1和起始位5的位(从右边数),交换的位数是3个,所以起始位1的3个位数111(从右边数), 起始位5的3个位数是001(从右边数),那么交换的结果就是r = 11100011 (二进制). 

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数说工作室

【SAS Says】基础篇:5. 开发数据(一)

本节目录: 开发数据 5.1 创建并重新定义变量 5.2 使用SAS函数 5.3 使用IF-THEN语句 5.4 用IF-THEN语句将观测值分组 5.5 构造...

3224
来自专栏用户2442861的专栏

对vector等STL标准容器进行排序操作

STL几乎封装了所有的数据结构中的算法,从链表到队列,从向量到堆栈,对hash到二叉树,从搜索到排序,从增加到删除......可以说,如果你理解了STL,你会...

2402
来自专栏Crossin的编程教室

【每周一坑】杨辉三角形

杨辉三角形,也称帕斯卡三角,其定义为:顶端是 1,视为(row0).第1行(row1)(1&1)两个1,这两个1是由他们上头左右两数之和 (不在三角形内的数视为...

2734
来自专栏玄魂工作室

Python数据结构与算法-在M个数中找K个最小的数

比如输入10,-9,0,100,90,1,4,-9;找到最小的3个数为:-9,-9,0

2201
来自专栏小樱的经验随笔

2017 Multi-University Training Contest - Team 1 1006&&HDU 6038 Function【DFS+数论】

Function Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 131072/131072 K...

2825
来自专栏数据结构与算法

P3808 【模版】AC自动机(简单版)

题目背景 这是一道简单的AC自动机模版题。 用于检测正确性以及算法常数。 为了防止卡OJ,在保证正确的基础上只有两组数据,请不要恶意提交。 题目描述 给定n个模...

2786
来自专栏人工智能LeadAI

讨厌算法的程序员 | 第五章 合并算法

本篇介绍的“合并”算法,是为后面学习“归并排序”的一个准备。合并算法是归并排序中的一个子算法,请注意两者之间的关系和差异。 之所以把它独立成一篇,一方面是一旦了...

3655
来自专栏TensorFlow从0到N

讨厌算法的程序员 5 - 合并算法

本篇介绍的“合并”算法,是为后面学习“归并排序”的一个准备。合并算法是归并排序中的一个子算法,请注意两者之间的关系和差异。 之所以把它独立成一篇,一方面是一旦...

3455
来自专栏算法修养

CodeForces 19D Points (线段树+set)

D. Points time limit per test 2 seconds memory limit per test 256 megabyte...

3679
来自专栏数据结构与算法

P3808 【模版】AC自动机(简单版)

题目背景 这是一道简单的AC自动机模版题。 用于检测正确性以及算法常数。 为了防止卡OJ,在保证正确的基础上只有两组数据,请不要恶意提交。 题目描述 给定n个模...

2955

扫码关注云+社区

领取腾讯云代金券