涉及位操作的算法辑录

た入场券 2022-05-23 02:49 127阅读 0赞

判断一个正整数X是否为2*N*，即是否为2的N次方(2，4，8，…)。除了使用循环语句（或者迭代）进行除2取余运算外，也可以采用位运算。考虑到2，4，8…这样的整数转化为二进制数是10，100，1000，…。如果X是2的*N*次方，比如2，4，8，那么X减1之后的二进制数则分别为1，11，111。与X作与运算，结果为零。利用此方法，可以写一个判断整数X是否为2的*N*次方的程序。

#include<iostream>
    using namespace std;
    
    int main(){
    	int x = 0;
    	while(1){
    		cout << "输入一个正整数： ";
    		cin >> x;
    		if(x&(x-1))
    			cout << x << "不是2的N次方整数！" << endl; 
    		else
    			cout << x << "是2的N次方整数！" << endl;
    	}
    	return 0;
    }

执行结果：

![70][]

求一个正整数X转化为二进制数后，包含的数字“1”的个数（包含0的个数须分多种情况讨论）。使用位运算来实现算法，考虑到整数X的二进制数减1之后，最右边的“1”位会变成“0”，而其之后原先所有的“0”将变成“1”。那么，每进行一次X&(X-1)，将消除二进制数中最右的一个“1”。这样，可以通过X&(X-1)运算直行至结果为0时的次数求出二进制数中“1”的个数。

#include<iostream>
    using namespace std;
    
    int func(int x);
    int main(){
        int x;
        while(1){
    		cout << "输入一个正整数:";
    		cin >> x;
    		cout << "转换为二进制数后包含 '1'的个数为:" << func(x) <<endl;
    	}
    	return 0;
    }
    
    int func(int a){
    	int count = 0;
    	while(a){
    		count ++;
    		a&=(a-1);
    	}
    	return count;
    }

执行结果：

![70 1][]

如何利用位运算实现整数的加减法呢？对于正整数X和Y，X&Y则是提取两者二进制数相同位值的与，这个结果是X、Y相同值位的二进制数的一半。而X^Y则是提取出X和Y不同位值的异或，得到结果是X、Y不同值位的二进制数。X+Y的结果可以看做相同值位二进制数与不同值位二进数之和。函数原型：

int Add(int x, int y){
    return((x&y)<<1)+(x^y);  //(x&y)<<1中<<1位移相当于乘以2；
    }

[70]: /images/20220523/3a1082956c9f4cd798f93dbfcaee7d4b.png
[70 1]: /images/20220523/f71245f3e272474aab919fbc32da75a2.png