我一直在尝试在业余时间学习C,而其他语言(C#、Java等)都有相同的概念(通常是相同的运算符)。。。
在核心层面,比特移位(<<,>>,>>)做什么,它可以帮助解决什么问题,以及弯道周围潜伏着什么陷阱?换言之,这是一个绝对的初学者指南,可以让你充分利用它的优点。
我一直在尝试在业余时间学习C,而其他语言(C#、Java等)都有相同的概念(通常是相同的运算符)。。。
在核心层面,比特移位(<<,>>,>>)做什么,它可以帮助解决什么问题,以及弯道周围潜伏着什么陷阱?换言之,这是一个绝对的初学者指南,可以让你充分利用它的优点。
当前回答
比特移位运算符正是其名称所暗示的。它们会移位。以下是对不同班次操作员的简要介绍(或不那么简单)。
操作员
>>是算术(或有符号)右移运算符。>>>是逻辑(或无符号)右移运算符。<<是左移位运算符,同时满足逻辑和算术移位的需要。
所有这些运算符都可以应用于整数值(int、long、可能的short和byte或char)。在某些语言中,对任何小于int的数据类型应用移位运算符会自动将操作数的大小调整为int。
注意,<<<不是运算符,因为它是多余的。
还要注意,C和C++不区分右移运算符。它们只提供>>运算符,正确的移位行为是为签名类型定义的实现。答案的其余部分使用C#/Java运算符。
(在所有主流的C和C++实现中,包括GCC和Clang/LLVM,对有符号类型的>>都是算术。一些代码假设这一点,但这不是标准所保证的。不过,这并不是未定义的;标准要求实现以某种方式定义它。然而,负有符号数字的左移是未定义的行为(有符号整数溢出)。因此,除非您需要算术右移,否则使用无符号类型进行位移位通常是一个好主意。)
左移(<<)
整数作为一系列位存储在存储器中。例如,存储为32位整数的数字6为:
00000000 00000000 00000000 00000110
将该位模式向左移动一个位置(6<<1)将产生数字12:
00000000 00000000 00000000 00001100
如您所见,数字向左移动了一个位置,右边的最后一个数字用零填充。您可能还注意到,向左移动相当于乘以2的幂。因此,6<<1相当于6*2,6<<3相当于6*8。一个好的优化编译器将在可能的情况下用移位替换乘法。
非循环移位
请注意,这些不是循环移位。将该值向左移动一个位置(3758096384<<1):
11100000 00000000 00000000 00000000
结果3221225472:
11000000 00000000 00000000 00000000
移动到“末尾”的数字丢失。它不会缠绕。
逻辑右移(>>)
逻辑右移与左移相反。它们不是向左移动比特,而是向右移动。例如,将数字12:
00000000 00000000 00000000 00001100
向右移动一个位置(12>>>1)将返回原来的6:
00000000 00000000 00000000 00000110
所以我们看到向右移动相当于除以2的幂。
丢失的比特不见了
然而,移位不能回收“丢失”的位。例如,如果我们改变这种模式:
00111000 00000000 00000000 00000110
向左4个位置(939524102<<4),我们得到2147483744:
10000000 00000000 00000000 01100000
然后向后移动((939524102<<4)>>4),我们得到134217734:
00001000 00000000 00000000 00000110
一旦丢失位,我们就无法恢复原始值。
算术右移(>>)
算术右移与逻辑右移完全相同,不同的是,它不是用零填充,而是用最高有效位填充。这是因为最高有效位是符号位,或区分正数和负数的位。通过用最高有效位填充,算术右移是保符号的。
例如,如果我们将此位模式解释为负数:
10000000 00000000 00000000 01100000
我们的电话号码是2147483552。用算术移位(-214743552>>4)将其向右移动4个位置,可以得到:
11111000 00000000 00000000 00000110
或号码134217722。
所以我们看到,通过使用算术右移而不是逻辑右移,我们保留了负数的符号。再一次,我们看到我们正在进行2次幂除法。
其他回答
比特移位运算符正是其名称所暗示的。它们会移位。以下是对不同班次操作员的简要介绍(或不那么简单)。
操作员
>>是算术(或有符号)右移运算符。>>>是逻辑(或无符号)右移运算符。<<是左移位运算符,同时满足逻辑和算术移位的需要。
所有这些运算符都可以应用于整数值(int、long、可能的short和byte或char)。在某些语言中,对任何小于int的数据类型应用移位运算符会自动将操作数的大小调整为int。
注意,<<<不是运算符,因为它是多余的。
还要注意,C和C++不区分右移运算符。它们只提供>>运算符,正确的移位行为是为签名类型定义的实现。答案的其余部分使用C#/Java运算符。
(在所有主流的C和C++实现中,包括GCC和Clang/LLVM,对有符号类型的>>都是算术。一些代码假设这一点,但这不是标准所保证的。不过,这并不是未定义的;标准要求实现以某种方式定义它。然而,负有符号数字的左移是未定义的行为(有符号整数溢出)。因此,除非您需要算术右移,否则使用无符号类型进行位移位通常是一个好主意。)
左移(<<)
整数作为一系列位存储在存储器中。例如,存储为32位整数的数字6为:
00000000 00000000 00000000 00000110
将该位模式向左移动一个位置(6<<1)将产生数字12:
00000000 00000000 00000000 00001100
如您所见,数字向左移动了一个位置,右边的最后一个数字用零填充。您可能还注意到,向左移动相当于乘以2的幂。因此,6<<1相当于6*2,6<<3相当于6*8。一个好的优化编译器将在可能的情况下用移位替换乘法。
非循环移位
请注意,这些不是循环移位。将该值向左移动一个位置(3758096384<<1):
11100000 00000000 00000000 00000000
结果3221225472:
11000000 00000000 00000000 00000000
移动到“末尾”的数字丢失。它不会缠绕。
逻辑右移(>>)
逻辑右移与左移相反。它们不是向左移动比特,而是向右移动。例如,将数字12:
00000000 00000000 00000000 00001100
向右移动一个位置(12>>>1)将返回原来的6:
00000000 00000000 00000000 00000110
所以我们看到向右移动相当于除以2的幂。
丢失的比特不见了
然而,移位不能回收“丢失”的位。例如,如果我们改变这种模式:
00111000 00000000 00000000 00000110
向左4个位置(939524102<<4),我们得到2147483744:
10000000 00000000 00000000 01100000
然后向后移动((939524102<<4)>>4),我们得到134217734:
00001000 00000000 00000000 00000110
一旦丢失位,我们就无法恢复原始值。
算术右移(>>)
算术右移与逻辑右移完全相同,不同的是,它不是用零填充,而是用最高有效位填充。这是因为最高有效位是符号位,或区分正数和负数的位。通过用最高有效位填充,算术右移是保符号的。
例如,如果我们将此位模式解释为负数:
10000000 00000000 00000000 01100000
我们的电话号码是2147483552。用算术移位(-214743552>>4)将其向右移动4个位置,可以得到:
11111000 00000000 00000000 00000110
或号码134217722。
所以我们看到,通过使用算术右移而不是逻辑右移,我们保留了负数的符号。再一次,我们看到我们正在进行2次幂除法。
包括位移位在内的按位操作是低级硬件或嵌入式编程的基础。如果您阅读设备规范或甚至某些二进制文件格式,您将看到字节、单词和dword,它们被分解为非字节对齐的位字段,其中包含各种感兴趣的值。访问这些位字段进行读/写是最常见的用法。
图形编程中的一个简单的实际示例是16位像素表示如下:
bit | 15| 14| 13| 12| 11| 10| 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| Blue | Green | Red |
要获得绿色值,您可以执行以下操作:
#define GREEN_MASK 0x7E0
#define GREEN_OFFSET 5
// Read green
uint16_t green = (pixel & GREEN_MASK) >> GREEN_OFFSET;
解释
为了获得从偏移量5开始到10结束(即6位长)的绿色ONLY值,您需要使用(位)掩码,当对整个16位像素应用该掩码时,将仅产生我们感兴趣的位。
#define GREEN_MASK 0x7E0
适当的掩码为0x7E0,二进制为00000111111000000(十进制为2016)。
uint16_t green = (pixel & GREEN_MASK) ...;
要应用掩码,请使用AND运算符(&)。
uint16_t green = (pixel & GREEN_MASK) >> GREEN_OFFSET;
应用掩码后,您将得到一个16位数字,这实际上只是一个11位数字,因为它的MSB位于第11位。绿色实际上只有6位长,因此我们需要使用右移(11-6=5)来缩小它,因此使用5作为偏移量(#define Green_offset 5)。
同样常见的是使用比特移位进行2次幂的快速乘法和除法:
i <<= x; // i *= 2^x;
i >>= y; // i /= 2^y;
位屏蔽和移位
位移位通常用于低级图形编程。例如,以32位字编码的给定像素颜色值。
Pixel-Color Value in Hex: B9B9B900
Pixel-Color Value in Binary: 10111001 10111001 10111001 00000000
为了更好地理解,相同的二进制值标记了什么部分代表什么颜色部分。
Red Green Blue Alpha
Pixel-Color Value in Binary: 10111001 10111001 10111001 00000000
举个例子,我们想得到这个像素颜色的绿色值。我们可以很容易地通过掩蔽和转移来获得该值。
我们的口罩:
Red Green Blue Alpha
color : 10111001 10111001 10111001 00000000
green_mask : 00000000 11111111 00000000 00000000
masked_color = color & green_mask
masked_color: 00000000 10111001 00000000 00000000
逻辑&运算符确保只保留掩码为1的值。我们现在要做的最后一件事,就是通过将所有这些位右移16位(逻辑右移)来获得正确的整数值。
green_value = masked_color >>> 16
瞧,我们有一个整数表示像素颜色中的绿色量:
Pixels-Green Value in Hex: 000000B9
Pixels-Green Value in Binary: 00000000 00000000 00000000 10111001
Pixels-Green Value in Decimal: 185
这通常用于编码或解码图像格式,如jpg、png等。
Python中一些有用的位操作/操作。
我用Python实现了Ravi Prakash的答案。
# Basic bit operations
# Integer to binary
print(bin(10))
# Binary to integer
print(int('1010', 2))
# Multiplying x with 2 .... x**2 == x << 1
print(200 << 1)
# Dividing x with 2 .... x/2 == x >> 1
print(200 >> 1)
# Modulo x with 2 .... x % 2 == x & 1
if 20 & 1 == 0:
print("20 is a even number")
# Check if n is power of 2: check !(n & (n-1))
print(not(33 & (33-1)))
# Getting xth bit of n: (n >> x) & 1
print((10 >> 2) & 1) # Bin of 10 == 1010 and second bit is 0
# Toggle nth bit of x : x^(1 << n)
# take bin(10) == 1010 and toggling second bit in bin(10) we get 1110 === bin(14)
print(10^(1 << 2))
我只写提示和技巧。它可能在测试和考试中有用。
n=n*2:n=n<<1n=n/2:n=n>>1检查n是否为2的幂(1,2,4,8,…):检查!(n和(n-1))获取n:n|=(1<<x)的第x位检查x是偶数还是奇数:x&1==0(偶数)切换x:x^(1<<n)的第n位