C语言位运算技巧大全

  1. 判断int型变量a是奇数还是偶数:
    a&1 = 0 偶数a&1 = 1 奇数
  2. 整数的平均值
    对于两个整数x,y,如果用 (x+y)/2 求平均值,会产生溢出,因为 x+y 可能会大于INT_MAX,但是我们知道它们的平均值是肯定不会溢出的,我们用如下算法:
  3. 判断int型变量a是奇数还是偶数
  4. 判断一个整数是不是2的幂,对于一个数 x >= 0,判断他是不是2的幂
  5. 不用temp交换两个整数
  6. 计算绝对值

     
  7. 取模运算转化成位运算 (在不产生溢出的情况下)
    a % (2^n) 等价于 a & (2^n – 1)
  8. 值转换
    if (x == a) x= b;

     else x= a;
    等价于 x= a ^ b ^ x;
  9. 二进制中1的个数
    方法1:考虑到n-1会把n的二进制表示中最低位的1置0并把其后的所有0置1,同时不改变此位置前的所有位,那么n&(n-1)即可消除这个最低位的 1。这样便有了比顺序枚举所有位更快的算法:循环消除最低位的1,循环次数即所求1的个数。此算法的时间复杂度为O(n的二进制表示中的1的个数),最坏 情况下的复杂度O(n的二进制表示的总位数)。

    方法2:

    通过下面四步来计算其二进制中1的个数二进制中1的个数。

    第一步:每2位为一组,组内高低位相加

    00 00 00 00 00 00 00 00 10 00 01 10 11 01 10 00

    → 00 00 00 00 00 00 00 00 01 00 01 01 10 01 01 00

    第二步:每4位为一组,组内高低位相加

    0000 0000 0000 0000 0100 0101 1001 0100

    → 0000 0000 0000 0000 0001 0010 0011 0001

    第三步:每8位为一组,组内高低位相加

    00000000 00000000 00010010 00110001

    → 00000000 00000000 00000011 00000100

    第四步:每16位为一组,组内高低位相加

    0000000000000000 0000001100000100

    → 0000000000000000 0000000000000111

     

  10. 计算两个数的最大值、最小值

     

  11. 把一个数数向上取2的n次幂

    原理:把最高位的1拷到所有低位去,再加1,加1后,所有低位都变成0,最高位进1。最前面的-1是为了使v本来就是2的n次幂的时候,也能得到正确的结果。

  12. 把一个整数向上取a的倍数(内存对齐)

     

  13. 大小写转换

     

  14. 给出一个问题:给你一个整形数组,这个数组中除了一个数字只出现一次外,其他数字都只出现两次,求出那个只出现一次的数字?
    要求:时间复杂度为O(n) , 空间复杂度为O(1)。解法:一个数出现两个,两个数相同,而相等两个数异或的值为0 , 所以,我们只需要把整个数组的数都异或一遍,我们就能得到只出现了一次的那个数字

     

  15. 现在这个数组中,有两个数只出现了一次,求出这两个数字,且时间、空间复杂度不变。

    如果根据第一个问题的解法,我们最后面也是得到了一个值,但这个值是那两个数字(只出现一次)的异或值。我们又不知道这个两个数字的任何一个,所以我们得不到这两个数字。

    如果我们把数组分割成2个数组,每个数组中只含有一个只出现一次的数字,再调用问题一的解法,我们就能得到结果。

    关键在于我们怎么来分割这个数组,且空间复杂度是O(1)?

    首先我们从头到尾依次异或数组中的每一个数字,得到的结果就是两个只出现一次数字的异或结果,因为这两个数字肯定不一样,所以得到的结果数字肯定不是0,也就是这个二进制数字钟至少有一位是1 , 我们在这个结果数字中华找到第一个为 1的位的位置,记为第n为,我们就通过第n位是不是1,一把这个数组分割成一个数组。

     

 

更全的位运算可参考http://graphics.stanford.edu/~seander/bithacks.html (英文)

留下评论

电子邮件地址不会被公开。 必填项已用*标注