C/C++ 中的位运算及其典型应用

短命女 2022-10-14 01:10 214阅读 0赞

# C/C++ 中的位运算及其典型应用 #

C/C++ 中提供了6种位运算，对于每一种都很好理解。位运算比较简单，但是如果能灵活应用往往能取得预想不到的效果。这里将不会一一介绍其定义，**这里的重点是介绍一些比较经典的应用**。如果对其定义还不是很熟悉的朋友可以参考[位运算][Link 1]。需要注意的是负数按补码形式参加位运算。

## 1. 按位与 ##

### 1.1 判断奇偶 ###

int x = 100;
        int y = 1;
        std::cout << x << (x & y ? " is odd" : " is even") << std::endl;

### 1.2 取指定位数的值 ###

上面的情况可以看作是取x最后一位的值，根据最后一位是0还是1来判断奇偶，更一般的我们可以通过控制y来提取不同位置的值。

int x = 0b111011;
        int y = 0b1111;
        std::cout << bitset<sizeof(int) * 8>(x & y) << std::endl;	// 00000000000000000000000000001011

### 1.3 判断2的整数幂 ###

int x = 64;
        int y = x - 1;
        std::cout << ((x & y) ? "no" : "yes") << std::endl; // yes

### 1.4 二进制数中1的个数（汉明权重问题） ###

可以参考[C语言-统计二进制数中1的个数-Hamming weight-汉明权重问题][C_-_1_-Hamming weight-]。

## 2. 按位或 ##

这个有一个比较经典的应用，比如对于一些标志位的表达。比如对于一张图片可能是彩色，可能是灰度图，图像的深度可能是8位，或者32位（当然还有其他，这里仅仅举例）。

比如00 表示8位灰度图。这里就是通过按位或来计算。

int x = 0b00;	// 灰度图
        int y = 0b10;	// 32位
        int a = x | y;
        switch(a){
        	case 0:
        		std::cout << "8 bits gray image";
        		break;
        	case 1:
        		std::cout << "8 bits color image";
        		break;
        	case 2:
        		std::cout << "32 bits gray image";
        		break;
        	case 3:
        		std::cout << "32 bits color image";
        		break;
        	default:
        		break;
        }

## 3. 取反 ##

### 3.1 正负数变换 ###

比如100变-100，可能有人觉得不就是加个符号，或者乘-1就可以了么，但是想想底层的实现呢？

int x = 100;
        int y = (~x) + 1;
        std::cout << y << std::endl;

当然借助这个操作，其实可以进一步拓展来求取绝对值。只需要先对符号位进行判断，如果是负数（符号位为1）则执行上面的代码变为正数即可。

### 3.2 圆整到某个数的整数倍 ###

在深度学习的图像预处理中可能会遇到需要将图像的尺寸圆整到网络步长（比如32）的整数倍的问题。这里可以借助取反和与操作实现。

#define ALIGN(num, align) (((num) + (align)-1) & ~((align)-1))
    
    int size = ALIGN(240, 64);
    std::cout << size << std::endl;	//256

## 4. 异或 ##

### 4.1 交换两个数字 ###

不借助第三个变量，交换两个变量的值，这是一个经典的题，解法比较多，其中一种就是借助异或操作。

int x = 100;
        int y = 20;
        if (x != y)  
        {  
            x ^= y;  
            y ^= x;  
            x ^= y;  
        }  
        std::cout << "x is " << x << ", y is " << y << std::endl;

### 4.2 加密 ###

根据异或操作的性质，可以用于加密。比如设置一个 key，对于一段二进制信息 msg，msg 与 key 异或就完成了加密，而再进行一次异或操作就完成了解密。

## 5. 左移 ##

在符号位不为1的情况下，左移相当于乘2。

### 5.1 二进制数高低位互换 ###

int x = 0b1010110100111111;
        int y = (x << 8) | (x >> 8);
        std::cout << bitset<sizeof(int) * 8> (y) << std::endl;

## 6. 右移 ##

对无符号数,右移时左边高位移入0；对于有符号的值,如果原来符号位为0（该数为正），则左边也是移入0。  
如果符号位原来为1(即负数)，则左边移入0还是1，要取决于所用的计算机系统。有的系统移入0,有的系统移入1。移入0的称为“逻辑移位”，即简单移位；移入1的称为“算术移位”。

[C语言-统计二进制数中1的个数-Hamming weight-汉明权重问题][C_-_1_-Hamming weight-] 中的”神人法“便是借助移位实现的。

## 参考 ##

*  [C++：位操作基础篇之位操作全面总结][C]
 *  [C++ 算法篇 位运算][C_ _]

[Link 1]: https://www.runoob.com/cplusplus/cpp-operators.html
[C_-_1_-Hamming weight-]: https://blog.csdn.net/kuweicai/article/details/53574215
[C]: https://www.cnblogs.com/zhoug2020/p/4978822.html
[C_ _]: https://blog.csdn.net/weixin_43736974/article/details/84543970