本文主要介绍原码、位运算的种类,以及常用的位运算的使用场景。
目录
1 原码、反码、补码
计算机中数的存储都是以二进制的形式存储的,数据的表示形式有原码、反码和补码。现在绝大多数计算机都使用补码表示法,补码表示将计算机中的减法运算转换成加法运算,统一了计算机。
原码,最高位表示符号位,0表示正数,1表示负数,其余位表示数值大小。例如,8位的+5的原码是00000101,-5的原码是10000101。
反码(ones' complement):正数的反码和原码相同,负数的反码是将原码中除符号位外的所有位按位取反。例如,+5的反码是00000101,-5的反码是11111010。
补码(two's complement):正数的补码和原码相同,负数的补码是将原码中除符号位外的所有位按位取反后加1。例如,+5的补码是00000101,-5的补码是11111011。
2 有符号和无符号数
a. 有符号数 signed ,首位为符号位,0正 1负 ,使用源码和反码表示,无法表示出(对于
8bit)-128,使用补码表示:10000000 表示-128,一般的机器都是补码表示法,范围为
- (2^(n-1)) ~ 2^(n-1) - 1
b. 无符号数 unsigned,表示的正数的范围会变大 ,范围 为0 ~ 2^n -1
c. 计算机中的补码将计算机中的减法运算统一为加法运算
d. 0是无符号数
具体搞懂有符号和无符号的加减和表示:(加减溢出后的结果)
8bit有符号和无符号数的对比:有符号范围-128~127 无符号范围:0~255
首先明确几乎所有的计算机都是补码表示法:
有符号数:(-128~127)
-128 的二进制补码 10000000
-127 的二进制补码 10000001
+127的二进制补码 01111111
+1 的二进制补码 00000001
-1 的二进制补码 11111111
补码将减法转换成加法,舍去溢出位
例子:
int8_t lp = -128-1; // 10000000 + 11111111 = 101111111 舍掉溢出为 01111111 故为127
printf("%d\n",lp); // 127
int8_t lp1 = 127+1; // 01111111 + 00000001 = 100000000 为 -128
printf("%d\n",lp1); // -128
有符号-128的诞生:用10000000来表示-128
int8_t kp = -127 -1; // 10000001 + 11111111 = 110000000 舍掉溢出为 10000000 故为-128
printf("%d\n",kp); // -128
无符号数:(0~255)非负数,没有符号
-1 的二进制补码 11111111(有符号)
+1 的二进制补码 00000001
+255的二进制补码 11111111
+128的二进制补码 10000000
+127的二进制补码 01111111
补码将减法转换成加法,舍去溢出位
例子:
uint8_t kp = 0-1; // 00000000 + 11111111 = 11111111 故为255
printf("%d\n",kp); // 255
uint8_t kp1 = 255+1; // 11111111 + 00000001 = 100000000 舍掉溢出为 00000000 故为0
printf("%d\n",kp1); // 0
3 位运算
位运算是一种按二进制位进行运算的方式,常用于清零、取指定位、判断奇偶、翻转等场景。常见的位运算有:与(&)、或(|)、非(~)、异或(^)和移位运算符(>)。 C语言基本的位操作符有与、或、异或、取反、左移、右移六种位运算符。如下表所示:
符号 | 描述 | 运算规则 |
& | 与 | 两个位都为1时,结果才为1(同1为,不同为0) |
| | 或 | 两个位都为0时,结果才为0(同0为0,不同为1) |
^ | 异或 | 两个位相同为0,相异为1(相同为0,不同为1) |
~ | 取反 | 0变1,1变0 |
<< | 左移 | 各二进位全部左移若干位,高位丢弃,低位补0 |
>> | 又移 | 各二进位全部右移若干位,对无符号数,高位补0,有符号数,各编译器处理方法不一样,有的补符号位(算术右移),有的补0(逻辑右移) |
详细解释:
与(&)运算:将两个二进制数的对应位进行与运算,结果为1则对应位相同,否则不同。例如,3和5的二进制表示分别为0011和0101,它们的与运算结果为0001,即1。
或(|)运算:将两个二进制数的对应位进行或运算,结果为1则至少有一个对应位为1,否则为0。例如,3和5的二进制表示分别为0011和0101,它们的或运算结果为0111,即7。
非(~)运算:对一个二进制数取反,即将所有位翻转。例如,3的二进制表示为0011,它的非运算结果为1100,即-4。
异或(^)运算:将两个二进制数的对应位进行异或运算,结果为1则对应位不同,否则相同。例如,3和5的二进制表示分别为0011和0101,它们的异或运算结果为0110,即6。
移位运算符(>):将一个二进制数的所有位向右移动指定位数,左边空出的位用0填充,右边多出来的位被丢弃。例如,将数字3的二进制表示向右移动两位得到0000,即0。
4 位运算符使用规则
(1)六种位运算只能用于整型数据,对float和double类型进行位操作会被编译器报错。
(2)逻辑运算与位运算的区别:逻辑运算是将参与运算的两个表达式整体的结果进行逻辑运算,而位运算是将参与运算的两个数据,按对应的二进制数逐位进行逻辑运算。逻辑运算符有逻辑与&&、逻辑或||、逻辑非!,位运算则有六种运算符,位与&、位或|、位异或^、位取反~、位左移<<、位右移>>。
(3)如果左移位数>=类型长度,在GCC环境下,GCC编译器会报警告,但实际左移位数为左移位数%(8 * sizeof(int))。例如:
int i = 1, j = 0x80000000; //设int为32位
i = i << 33; // 33 % 32 = 1 左移1位,i变成2
j = j << 33; // 33 % 32 = 1 左移1位,j变成0,最高位被丢弃
(4)在C语言中,左移是逻辑/算术左移(两者完全相同),右移是算术右移,会保持符号位不变。
左移时总是移位和补零。右移时无符号数是移位和补零,此时称为逻辑右移;而有符号数大多数情况下是移位和补最左边的位(也就是补最高有效位),移几位就补几位,此时称为算术右移。 算术移位是相对于逻辑移位,它们在左移操作中都一样,低位补0即可,但在右移中逻辑移位的高位补0而算术移位的高位是补符号位。
右移对符号位的处理和左移不同,对于有符号整数来说,比如int类型,右移会保持符号位不变。符号位向右移动后,正数的话补0,负数补1,也就是汇编语言中的算术右移。当移动的位数超过类型的长度时,会取余数,然后移动余数个位。
int i = 0x80000000;
i = i >> 1; //i的值不会变成0x40000000,而会变成0xc0000000
上述代码移位后的结果是0xc0000000,因为有符号数的算术右移,需要保持符号位不变,所以补符号位。
(5)位操作符的运算优先级比较低,因为尽量使用括号来确保运算顺序,否则很可能会得到莫明其妙 的结果。比如要得到像1,3,5,9这些2^i+1的数字。写成int a = 1 << i + 1;是不对的,程序会先执行i + 1,再执行左移操作。应该写成int a = (1 << i) + 1。
4.1 逻辑移位和算术移位
4.1.1 逻辑左移和算法左移
逻辑左移和算术左移的区别主要在于它们处理二进制数的高位的方式。对于逻辑左移,右边会补0;而对于算术左移,右边不仅补0,还会根据原始数值的符号位进行填充。例如,对于二进制数10101011,逻辑左移一位后得到01010110,而算术左移一位后则得到11010110。
4.1.2 逻辑右移和算术右移
逻辑右移和算术右移之间也存在显著差异。在逻辑右移中,左边会补0,而在算术右移中,左边会填入符号位。这意味着,如果原始数值是有符号数,算术右移会保持原始数的符号位不变,而逻辑右移则不会。
4.1.3 总结
逻辑移位和算术移位的主要区别在于它们如何对待被移出的位。逻辑移位主要用于无符号数的操作,而算术移位则用于有符号数的操作,以保持数值的准确性。逻辑移位仅仅是移位不会考虑符号位,而算术移位会保留符号位的准确。
对于一个有符号数-3和3 的一些移位操作:
{
// 负数的补码表示法: 除符号位其他位反码+1
// -3的二进制原码: 10000000000000000000000000000011
// -3的二进制反码: 11111111111111111111111111111100
// -3的二进制补码: 11111111111111111111111111111101
int a = -3; // 二进制表示为 11111111111111111111111111111011
int b = 3;
cout << " 描述 " << " 二进制 " << " 十进制 " << " 十六进制 " << endl;
cout << "+3的补码 : " << bitset<32>(b) << " " << hex << b << " " << dec << b << endl;
cout << "-3的补码 : " << bitset<32>(a) << " " << hex << a << " " << dec << a << endl;
a = a << 2; // 左移2位,结果为 -6,二进制表示为 11111111111111111111111111110000
cout << "-3左移2位: " << bitset<32>(a) << " " << hex << a << " " << dec << a << endl;
b = b << 2;
cout << "+3左移2位: " << bitset<32>(b) << " " << hex << b << " " << dec << b << endl;
a = -3;
a = a >> 2; // 右移2位,结果为 -3,二进制表示为 11111111111111111111111111100000
cout << "-3右移2位: " << bitset<32>(a) << " " << hex << a << " " << dec << a << endl;
b = 3;
b = b >> 2;
cout << "+3右移2位: " << bitset<32>(b) << " " << hex << b << " " << dec << b << endl;
}
运行结果:
描述 二进制 十六进制 十进制
+3的补码 : 00000000000000000000000000000011 3 3
-3的补码 : 11111111111111111111111111111101 fffffffd -3
-3左移2位: 11111111111111111111111111110100 fffffff4 -12
+3左移2位: 00000000000000000000000000001100 c 12
-3右移2位: 11111111111111111111111111111111 ffffffff -1
+3右移2位: 00000000000000000000000000000000 0 0
分析结果可以很清晰的理解有符号数的算术移位的补全符号位的操作。
4.2 位运算的应用场景
以下是一些常见的应用场景:
- 位掩码:使用位与运算符(&)和位或运算符(|),可以快速地将某些位置0或保留。
- 求反:使用按位非运算符(~),可以将二进制数反转,例如对一个数取反偶数次结果是它本身,常用场景包括求相反数。
- 判断奇偶性:通过对int型变量与1进行与运算,如果结果为0则为偶数,如果结果为1则为奇数。
- 提取特定位:通过右移和与运算,可以提取int型变量的特定位,例如a>>k&1可以获取a的第k位的值。
- 设置特定位:通过左移和或运算,可以将int型变量的特定位设置为1,例如a|(1<
- 大量数据的高效处理:位运算可以直接对内存中的二进制位进行操作,因此在处理大量数据时,位运算可以提高程序的运行效率。
- 驱动开发中的置0和置1:在驱动开发中,经常需要指定的位数发生变化,又不能改变其它位的值,这时候位运算的技巧就显得非常重要了。
5 位运算的详细使用
5.1 字节序介绍
C语言的字节序一般从左到右是:高字节->低字节。
高位字节--->低位字节 0x11223344,从左到右,由高位字节到低位字节 因此bit的顺序是从右到左递增的 (... bit9 bit8 bit7 bit7 bit5 bit4 bit3 bit2 bit1 bit0)。
因此bit的序列从右到左是递增的。
5.2 应用
主要使用& 和 |,bit0为第一位
5.2.1整数的第N位 置1或者0
1 置某位不变:
a 只需要 该位与 0 进行或运算(似乎不变就可以了)
#define SET_BIT_N_NO_CHANGE(X,N) ((X) | (0U << ((N) - 1)))
2 置某位为1,其他位不变:
a 只需要 该位与 1 进行或运算
#define SET_BIT_N(X,N) ((X) | (1U << ((N)-1)))
3 置某位为0,其他位不变:
a 设置相同位数的一个无符号数,置该位为 1 ,然后对该数进行取反,取反后的数与原数进行相与即可。
#define CLEAR_BIT_N(X,N) ((X) & (~(1U << ((N)-1))))
5.2.2 整数的一段位置1或者0
1 将32位数x的第n位到第m位置1(特定数据段置1)
#define SET_BITS_N_M(x,n,m) ((x) | (((~0U)>>(32-((m)-(n)+1)))<<((n)-1)))
2 将32位数x的第n位到第m位置0(特定数据段置0)
#define CLEAR_BITS_N_M(x,n,m) ((x) & (~(((~0U)>>(32-((m)-(n)+1)))<<((n)-1))))
3 取32位数的第n位到第m位(取特定数据段的数)
#define GET_BITS_N_M(x,n,m) (((x) & ~(~(0U)<<((m)-(n)+1))<<((n)-1))>>((n)-1))
4 保留32位数的第n位到第m位,其他的置0(保留特定数据段,其他位置0)
#define REMAIN_BITS_N_M(x,n,m) ((x) & (((~0U) >> (32-((m)-(n)+1))) << ((n)-1)))
5.2.3 奇偶性判断
由二进制数可知,二进制bit0为0为偶数,为1为奇数,因此可以使用 if (( a & 1) == 0) ,则a为偶数,反之为奇数;可以替代if ((a % 2) == 0)。
5.2.4 特定位翻位
对于一个整数a ,a^1是翻位,a^0是a保持不变
一般用异或实现,如下对int a = 234; 对a的低8位进行翻位,a = a^0xff;
如下:
{
__LOG__("异或运算");
int a = 234;//000000000000000000000000 11101010
cout << "二进制: " << bitset<32>(a) << hex << " 十六进制: " << a << dec << " 十进制: " << a << endl;
a = a ^ 0xff;//000000000000000000000000 00010101
cout << "二进制: " << bitset<32>(a) << hex << " 十六进制: " << a << dec << " 十进制: " << a << endl;
}
运行结果:
*****************异或运算*****************
二进制: 00000000000000000000000011101010 十六进制: ea 十进制: 234
二进制: 00000000000000000000000000010101 十六进制: 15 十进制: 21
5.2.5 交换数据(不使用第三方变量)
int a = -12;
int b = 34;
a = a^b;
b = a^b;
a = a^b;
简单分析下为什么可以交换,如下:
int a = -12;
int b = 34;
a1 = a^b;
b1 = a1^b;
a2 = a1^b1;
最终 b1 和 a2 是输出结果,我们来具体看下:
b1 = a1^b = a^b^b = a^0 = a
a2 = a1^b1 = a^b^(a1^b) = a^b^(a^b^b)= a^a^b^b^b=b^0 = b
至此,交换完毕,这里用到异或运算的交换律和结合律,可以看出让a1和a2用a替代,b1用b替代并不会改变运算结果。
5.2.6 符号的变换(将一个整数变为负数)
取反+1即是原数的相反数,仅仅针对有符号数对于 int a; a的相反数为(~a) + 1。
int a = 34;
int a1 = (~(a)) + 1;//-34
5.2.7 求绝对值
无符号数的绝对值就是本身,有符号数的绝对值的求法,求int 类型数的绝对值:
// 求有符号数的绝对值
#define GET_ABSOLUTE_VALUE(a) ((((a)>>31)==0) ? (a) : ((~(a))+1))
// a为负数时
a >> 31 为 -1
// a为正数时
a >> 31 为 0
5.2.8 一些操作实例
unsigned int i = 0x00ff1234;
//i |= (0x1<<13);//bit13置1
//i |= (0xF<<4);//bit4-bit7置1
//i &= ~(1<<17);//清除bit17
//i &= ~(0x1f<<12);//清除bit12开始的5位
//取出bit3-bit8
//i &= (0x3F<<3);//保留bit3-bit8,其他位清零
//i >>= 3;//右移3位
//给寄存器的bit7-bit17赋值937
//i &= ~(0x7FF<<7);//bit7-bit17清零
//i |= (937<<7);//bit7-bit17赋值
//将寄存器bit7-bit17的值加17
// unsigned int a = i;//将a作为i的副本,避免i的其他位被修改
// a &= (0x7FF<<7);//取出bit7-bit17
//a >>= 7;//
// a += 17;//加17
// i &= ~(0x7FF<<7);//将i的bit7-bit17清零
// i |= (a<<7);//将+17后的数写入bit7-bit17,其他位不变
//给一个寄存器的bit7-bit17赋值937,同时给bit21-bit25赋值17
i &= ~((0x7FF<<7) | (0x1F<<21));//bit7-bit17、bit21-bit25清零
i |= ((937<<7) | (17<<21));//bit7-bit17、bit21-bit25赋值
5.2.9 给定整数N,判断是否是2的整数次幂。
// 要求N 大于0
#define IS_2_N(N) ( (((N) & ((N)-1))==0) ? true : false )
5.2.10 交换一个32位无符号数的前后16bit位
// 交换一个32位无符号数的前后16bit位
#define SWAP_A16_B16(X) (((X) >> 16) | ((X) << 16))
5.2.11 两数平均(防溢出)
inline int average1(int x, int y)
{
return (x >> 1) + (y >> 1) + (x & y & 1);
}
inline int average2(int x, int y)
{
return (x & y) + ((x ^ y) >> 1);
}
5.2.12 求一个数的二进制中1的个数
int popcount(int x)
{
int res = 0;
for(; x; x&=x-1) res ++;
return res;
}
5.2.13 打印出二进制数
void binary_to(int num)
{
cout << "二进制: ";
for (int i = 31; i >= 0; i--) {
if ((num & (1 << i)) != 0) {
cout << "1";
} else {
cout << "0";
}
}
cout << endl;
}
5.2.14 无符号bit位翻转
uint32_t reverse_bit(uint32_t value)
{
uint32_t num = 0;
int i = 0;
for (i = 1; i < 32; i++)
{
num += value & 1;
num <<= 1;
value >>= 1;
}
return num;
}
5.2.15 整数的除法运算
舍掉小数部分:(有符号和无符号都是一样的操作)
// 除以256
int a = 2345;
a = a >> 8
uint32_t b = 2345;
b = b >> 8;
四舍五入法:
无符号数
// 除以256
uint32_t a = 2345;
a = (a + 128) >> 8;
有符号数
// 除以256
int a = 2345;
a = (a + 128) >> 8;