算法：位运算

野性酷女 2022-06-16 20:41 324阅读 0赞

http://[blog.csdn.net/pipisorry/article/details/70318778][blog.csdn.net_pipisorry_article_details_70318778]

## 位操作基础 ##

位操作是程序设计中对位模式或二进制数的一元和二元操作。lz所以3进制在一般计算机应该不能进行位操作吧。

基本的位操作符有与、或、异或、取反、左移、右移这6种，它们的运算规则如下所示：

<table> 
 <tbody> 
 <tr> 
 <td>符号</td> 
 <td>&nbsp;描述</td> 
 <td>&nbsp;运算规则</td> 
 </tr> 
 <tr> 
 <td>&amp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</td> 
 <td>&nbsp;与</td> 
 <td>两个位都为1时，结果才为1</td> 
 </tr> 
 <tr> 
 <td>|&nbsp;&nbsp;</td> 
 <td>&nbsp;或&nbsp;&nbsp;&nbsp;&nbsp;</td> 
 <td>两个位都为0时，结果才为0</td> 
 </tr> 
 <tr> 
 <td>^&nbsp;&nbsp;&nbsp;&nbsp; </td> 
 <td>异或</td> 
 <td>两个位相同为0，相异为1</td> 
 </tr> 
 <tr> 
 <td>~&nbsp;&nbsp;&nbsp; </td> 
 <td>取反</td> 
 <td>0变1，1变0</td> 
 </tr> 
 <tr> 
 <td>&lt;&lt;&nbsp; </td> 
 <td>左移</td> 
 <td>各二进位全部左移若干位，高位丢弃，低位补0</td> 
 </tr> 
 <tr> 
 <td>&gt;&gt;&nbsp;</td> 
 <td>右移</td> 
 <td>各二进位全部右移若干位，对无符号数，高位补0，有符号数，各编译器处理方法不一样，有的补符号位（算术右移），有的补0（逻辑右移）</td> 
 </tr> 
 </tbody> 
</table>

[皮皮blog][blog]

## 除2的幂和对2的幂取模    ##

可以用位实现的 
对于除法,我们用>>运算符实现,对于数N,N>>m的结果就是N/(2^m) 
对于取模,我们用N=N&((1<<K)-1),这是对2^K取模

N=N&((1<<K)-1)取模比N % (2 \*\* K)快1倍左右（python下）

Note:运算符<<比-优先级要低，所以必须加()！！

## 在一个指定的32位二进制数的指定位 置1 ##

直接用N|(1<<m),就可以在N的第m位上置1了

将int型变量a的第k位清0，即a=a&~(1<<k)

[皮皮blog][blog]

## 快速判断一个数是否是M的幂次方 ##

要注意考虑输入是负数和0的情况！

通用方法

**方法1：**最直接的方法就是不停地除以M，看最后的余数是否为1；O(logMn)?

if(n>1)
            while(n%M==0) n /= M;
     return n==1;

递归：

public boolean isPowerOfThree(int n) {
        return n>0 && (n==1 || (n%3==0 && isPowerOfThree(n/3)));
    }

**方法2：**M^k次方一定能被最大的M^maxk (<2^32)整除。O(1)。

maxPowerOfM = int(pow(m, (int)(log(0x7fffffff) / log(m)))) \[[数学计算相关算法 ][Link 1]\]

maxPowerOfM% n == 0

**方法3：**利用对数换底公式logMn = logcn / logcM来做，那么如果n是M的幂数，则logMn一定是整数。O(1)的，但是一般比最优的方法慢一点。

Note:

1 如果logcM不精确的话，可能结果就不是整数了。所以c一般选择10，不能随便选！！！

2 n超出2\*\*32也会出错。

3 lz有个问题没时间弄明白，log10及log2在计算机中是如何计算出来的，为什么log10能AC不会出错而log2会因为精度出错呢？？？

那么如果n是3的幂数，则log3n一定是整数，我们利用换底公式可以写为log3n = log10n / log103，注意这里一定要用10为底数，不能用自然数或者2为底数，否则当n=243时会出错，原因请看[这个帖子][Link 2]。现在问题就变成了判断log10n / log103是否为整数，在c++中判断数字a是否为整数，我们可以用 a - int(a) == 0 来判断。

当然python中可以直接指定底数为M来计算（但是应该也是通过换底公式做的），\_\_import\_\_('math').log(num, M)，所以要使用\_\_import\_\_('math').log10(num)/...。

**方法4：**M很大的话可以枚举 O(logMmaxnum)

for such kind of `power` questions, if we need to check many times, it might be a good idea to store the desired powers into an array first.

如3的幂次方

public boolean isPowerOfThree(int n) {
        int[] allPowerOfThree = new int[]{1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907, 43046721, 129140163, 387420489, 1162261467};
        return Arrays.binarySearch(allPowerOfThree, n) >= 0;
    }

**方法5：**转换到M进制，看是否只有一个1

The idea is to convert the original number into radix-3 format and check if it is of format `10*` where `0*` means `k` zeros with `k>=0`.

如转换成3进制判断。

public boolean isPowerOfThree(int n) {
        return Integer.toString(n, 3).matches("10*");
    }

Note: 不过转换成M进制的过程很可能是辗转相除法得到的，类似方法1，所以lz觉得应该是O(n)的。

### 快速判断一个数是否是2的幂次方 ###

**思路1：最快速的方法 Time complexity = O(1) lz推荐**

(number & number - 1) == 0

将2的幂次方写成二进制形式后，很容易就会发现有一个特点：二进制中只有一个1，并且1后面跟了n个0； 因此问题可以转化为判断1后面是否跟了n个0就可以了。

如果将这个数减去1后会发现，仅有的那个1会变为0，而原来的那n个0会变为1；因此将原来的数与去减去1后的数字进行与运算后会发现为零。

原因：因为2的N次方换算是二进制为10……0这样的形式(0除外)。与上自己-1的位数，这们得到结果为0。例如。8的二进制为1000；8-1=7，7的二进制为111。两者相与的结果为0。计算如下：

1000  
     & 0111  
        -------  
        0000

**思路2：同样快速但是不是最好的方法 Time complexity = O(1)**

2^k次方一定能被最大的2^32整除。

Because the range of an integer = -2147483648 (-2^31) ~ 2147483647 (2^31-1), the max possible power of two = 2^30 = 1073741824.

(1) If n is the power of two, let n = 2^k, where k is an integer. We have 2^30 = (2^k) \* 2^(30-k), which means (2^30 % 2^k) == 0.

(2) If n is not the power of two, let n = j\*(2^k), where k is an integer and j is an odd number. We have (2^30 % j\*(2^k)) == (2^(30-k) % j) != 0.

return n>0 && (1073741824 % n == 0);

**思路3：使用bitcount计算有多少个1，只有一个1说明是2的幂次方**

Note: 一位一位的数就可以知道具体是多少次方了。

### 快速判断一个数是否是4的幂次方 ###

4的整数次幂的二进制数都为 (4)100、(16)10000、(64)1000000......

**思路1：**

将4的幂次方写成二进制形式后，很容易就会发现有一个特点：二进制中只有一个1（1在奇数位置），并且1后面跟了偶数个0； 因此问题可以转化为判断1后面是否跟了偶数个0就可以了。

** 思路2：lz推荐**

4的幂次方4^n也可以写为2^(2\*n)，即也可以写为2的幂次方，当然就满足2的幂次方的条件了，即num & num-1==0。

首先用条件num & num-1==0来判断是否为2的幂次方，若不满足，则不是。若满足，在用条件num & 0x55555555来判断，若为真，则这个整数是4的幂次方，否则不是。

return num > 0 and (num & num - 1) == 0 and (num & 0x5555555555555555) != 0

或者return ((num-1)&num)==0 && (num-1)%3==0;

Note: 后一种是因为

![Center][] (3 + 1)^n; 如果是2^(2k+1)就不能%3=0了。

### 快速判断一个数是否是3的幂次方 ###

方法1：通用方法。lz推荐

由于输入是int，正数范围是0-231，在此范围中允许的最大的3的次方数为`maxPowerOfThree =`319=1162261467，那么我们只要看这个数能否被n整除即可；

方法2：通用方法。利用对数公式。把该整数对3取对数，如果结果是整数，说明该整数是3的幂。

\[[Power of Three 判断3的次方数][Power of Three _3]\]

\[[summary-of-all-solutions][]\]

## 算法-求二进制数中1的个数 ##

**移位计数法**

循环右移，判断最低位是否为1，是则+1。运算次数与输入n最高位1的位置有关，最多循环32次。

int BitCount(unsigned int n)
    {
        unsigned int c =0 ; // 计数器
        while (n >0)
        {
            if((n &1) ==1) // 当前位是1
                ++c ; // 计数器加1
            n >>=1 ; // 移位
        }
        return c ;
    }

一个更精简的版本如下

int BitCount1(unsigned int n)
    {
        unsigned int c =0 ; // 计数器
        for (c =0; n; n >>=1) // 循环移位
            c += n &1 ; // 如果当前位是1，则计数器加1
        return c ;
    }

**快速法**

此算法来源于上面提到的 “快速判断一个数是否是2的幂次方”，n&(n-1)可以用于判断一个数的二进制是否只有一个1，而n=n&(n-1) 能移除掉n的二进制中最右边的1的性质，循环移除，直到将1全部移除，这种方法将问题的复杂度降低到只和1的个数有关系，即其运算次数与输入n的大小无关，只与n中1的个数有关。如果n的二进制表示中有k个1，那么这个方法只需要循环k次即可。其原理是不断清除n的二进制表示中最右边的1，同时累加计数器，直至n为0。

int BitCount2(unsigned int n)
    {
        unsigned int c =0 ;
        for (c =0; n; ++c)
        {
            n &= (n -1) ; // 清除最低位的1
        }
        return c ;
    }

与其等价的另一个快速法：n -= n &(~n + 1)，每次进行这个操作时，也是移除最右侧1的过程。

Note: n &(~n + 1) 这个是经典的得到n中最右侧1的操作。如n = 01000100，则n &(~n + 1) = 00000100。

**平行算法（lz推荐，测试比快速法快）**

类似归并过程，组与组之间的数量合并成一个大组，进行下一步归并。

int BitCount4(unsigned int n) 
    { 
        n = (n &0x55555555) + ((n >>1) &0x55555555) ; 
        n = (n &0x33333333) + ((n >>2) &0x33333333) ; 
        n = (n &0x0f0f0f0f) + ((n >>4) &0x0f0f0f0f) ; 
        n = (n &0x00ff00ff) + ((n >>8) &0x00ff00ff) ; 
        n = (n &0x0000ffff) + ((n >>16) &0x0000ffff) ; 
    
        return n ; 
    }

速度不一定最快，但是想法绝对巧妙。思路是先将n写成二进制形式，然后相邻位相加，重复这个过程，直到只剩下一位。

lz多解释一下：

n = (n &0x55555555) + ((n >>1) &0x55555555)的结果描述了每两个bit成一组1的数量分布。

以n = -1 即 (1111 1111 1111 1111 1111 1111 1111 1111)为例，n >>1后再与n相加时，每隔一位是没用的，不应该算的，所以每两位一组时要使用01（0x55555555就是(0101 0101 0101....)）来屏蔽，其结果为 (1010 1010 1010 1010 1010 1010 1010 1010)，可以看到每两个 bit成一组1的数量为(10)即2个。

![Center 1][]

n = (n &0x33333333) + ((n >>2) &0x33333333) ; 以n = -1 即上一步结束后 (1010 1010 1010 1010 1010 1010 1010 1010)，n >>2后再与n相加时，每隔2位是没用的，不应该算的，所以每2位一组时需要使用0011（0x33333333就是(0011 0011 0011....)）来屏蔽，其结果为 (0011)，可以看到每两个 bit成一组1的数量为(10)即2个。

![Center 2][]

那么n = (n &0x0f0f0f0f) + ((n >>4) &0x0f0f0f0f) ; 就是使用00001111 = 0x0f来屏蔽的。

同理n = (n &0x00ff00ff) + ((n >>8) &0x00ff00ff) ;     n = (n &0x0000ffff) + ((n >>16) &0x0000ffff) ; 的结果分别描述了每2， 4， 8， 16个bit成一组1的数量分布。

类似的以217（11011001）为例，以树形图来说明。217的二进制表示中有5个1。

![2010060623161414.jpg][]

不过为了不重复相加，要设计好几个常数，这点太麻烦了。

还有查表法，完美法，位标志法，指令法，MIT hackmem算法等等。

\[[编程之美求二进制中1的个数][1]\]

\[[算法-求二进制数中1的个数][-_1]\]\*

\[[Hacker's Delight][Hacker_s Delight]\]

**拓展问题**

给定两个正整数（二进制形式表示）A和B，问把A变为B需要改变多少位（bit）？也就是说，整数A 和B 的二进制表示中有多少位是不同的？

分为两步，(1)将A和B异或得到C，即C=A^B，(2)计算C的二进制中有多少个1。

## 求比x大且是2的n次方的数 ##

当一个无符号的整数x是非2的次方数时怎么求得大于x的最接近x的并且是2的n次方的那个数？

**方法1：**

x|=x>>1;  
x|=x>>2;  
x|=x>>4;  
x|=x>>8;  
x|=x>>16;  
x+=1;

经过上面6步运算后可以求得。

def power2n(x):
        '''
        求比x大(或相等)且是2的n次方的数
        '''
        if x > 0 and (x & x - 1) == 0:  # x正好是2的n次方的数
            return x
        for i in (1, 2, 4, 8, 16, 32):  # 支持到64位int型，加上64则可以支持到128等等
            x |= x >> i
        # print(x + 1)
        return x + 1

方法原理

要想求得比x大且是2的n次方的数，我们只需要知道x的2进制最高位的是1的位置，假设这个位置为index，那么比x大且是2的n次方的数就是index+1为1且0到index的所有低位都为0的2进制数就是我们要求的。例如：(0000，0100，0000，0000，0000，0000，0000，0001)2  这是一个数的2进制形式，那么比该数大且是2的n次方的数应该是：(0000，1000，0000，0000，0000，0000，0000，0000)2。

我们再回过来看上面的方法，上面的方法是将该数2进制最左边为1的右边所谓位为0的都变成1。还是以(0000，0100，0000，0000，0000，0000，0000，0001)2为例。就是要将标记为红色的1的右边所有为0的位都变成1然后在此基础上加1就为我们所求得的数即(0000，0111，1111，1111，1111，1111，1111，1111)2+1为最终的结果。

那么我们来看看上面的6步是怎么做到的。我们将一个数的2进制分成了8份，每份4位，那么x|=x>>1 x|=x>>2;将最高位为1右边的3位全变成了1至于其他位置为1在这两个操作下会有什么影响我们不管。(0000，0100，0000，0000，0000，0000，0000，0001)2  最高位1的右边3位所有为0的都变成1。如果本身为1则不变。(0000，0111，1000，0000，0000，0000，0000，0001)2  接下来的x|=x>>4会将最高位为1右边7个位置所有为0的都变成1。这样最左边就会有8个为1的位了。接下来的x|=x>>8，x|=x>>16。最终会将右边所有的位都变成1。

Note：这里是没有考虑溢出的。如果是最高位置为1的话那么就会发生溢出。

**方法2：**

lz觉得这样也可以，2^(\[logN\])，\[\]表示log后向上取整（注意向上取整 != 向下取整+1）。但是log函数计算应该是数值方法计算出来的，可能不准确也更慢。

[皮皮blog][blog]

## 判断奇偶 ##

只要根据最未位是0还是1来决定，为0就是偶数，为1就是奇数。因此可以用if ((a & 1) == 0)代替if (a % 2 == 0)来判断a是不是偶数。 
下面程序将输出0到100之间的所有奇数。 
    for (i = 0; i < 100; ++i) 
        if (i & 1) 
            printf("%d ", i); 
    putchar('\\n');

## 不用额外变量交换两整数的值 ##

一般的写法是：  
    void Swap(int &a, int &b)  
    \{  
        if (a != b)  
        \{  
            int c = a;  
            a = b;  
            b = c;  
        \}  
    \}  
可以用位操作来实现交换两数而不用第三方变量：  
    void Swap(int &a, int &b)  
    \{  
        if (a != b)  
        \{  
            a ^= b;  
            b ^= a;  
            a ^= b;  
        \}  
    \}  
可以这样理解：  
第一步  a^=b 即a=(a^b);  
第二步  b^=a 即b=b^(a^b)，由于^运算满足交换律，b^(a^b)=b^b^a。由于一个数和自己异或的结果为0并且任何数与0异或都会不变的，所以此时b被赋上了a的值。  
第三步 a^=b 就是a=a^b，由于前面二步可知a=(a^b)，b=a，所以a=a^b即a=(a^b)^a。故a会被赋上b的值。  
再来个实例说明下以加深印象。int a = 13, b = 6;  
a的二进制为 13=8+4+1=1101(二进制)  
b的二进制为 6=4+2=110(二进制)  
第一步 a^=b  a = 1101 ^ 110 = 1011;  
第二步 b^=a  b = 110 ^ 1011 = 1101;即b=13  
第三步 a^=b  a = 1011 ^ 1101 = 110;即a=6

绘制一个更好的图理解方式

![Center 3][]

[皮皮blog][blog]

from: [http://blog.csdn.net/pipisorry/article/details/70318778][blog.csdn.net_pipisorry_article_details_70318778]

ref: \[[位操作基础篇之位操作全面总结][Link 3]\]

[blog.csdn.net_pipisorry_article_details_70318778]: http://blog.csdn.net/pipisorry/article/details/70318778
[blog]: http://blog.csdn.net/pipisorry
[Link 1]: http://blog.csdn.net/pipisorry/article/details/46008603
[Link 2]: https://leetcode.com/discuss/78532/summary-all-solutions-new-method-included-at-15-30pm-jan-8th
[Center]: /images/20220617/90fb7f52ef5a45b6a12e4039b7b24a11.png
[Power of Three _3]: http://www.cnblogs.com/grandyang/p/5138212.html
[summary-of-all-solutions]: https://discuss.leetcode.com/topic/33536/a-summary-of-all-solutions-new-method-included-at-15-30pm-jan-8th
[Center 1]: /images/20220617/70b3a1df13cd466ab0f889cb83eb40c2.png
[Center 2]: /images/20220617/e0f6ca5ccb16491d854c635b2ac2ca96.png
[2010060623161414.jpg]: /images/20220617/d81b98506b09407f8b9e959b8beb0631.png
[1]: http://www.cnblogs.com/youxin/p/3233954.html
[-_1]: http://www.cnblogs.com/graphics/archive/2010/06/21/1752421.html
[Hacker_s Delight]: http://www.hackersdelight.org/hdcodetxt/pop.c.txt
[Center 3]: /images/20220617/9f24b66c5e3e4ef48129ccc77749810e.png
[Link 3]: http://blog.csdn.net/morewindows/article/details/7354571