英文:
Difference between some operators "|", "^", "&", "&^". Golang
问题
最近我阅读了Golang规范,并遇到了一些有趣的运算符:
& 按位与 整数
| 按位或 整数
^ 按位异或 整数
&^ 按位清除 (AND NOT) 整数
我尝试了一下,但我只理解了"|"运算符用于整数相加,而"+"运算符还可以用于浮点数、字符串等。
在实践中,它们用于什么?有人能对上述这4个运算符给出一些解释吗?
英文:
Recently I read golang specification and faced with some interesting operators:
& bitwise AND integers
| bitwise OR integers
^ bitwise XOR integers
&^ bit clear (AND NOT) integers
I've tried to play with it, but the only one I have understood is that "|" add integers and "+" operator additionally work with floats, strings etc.
What they are used for in practice? Could anyone give some explanation about these 4 operators above?
答案1
得分: 44
按位运算符在处理字节级或位级数据时发挥作用。
这里列举了一些使用位运算的示例(无特定顺序):
1. 它们在密码学和哈希函数(例如MD5)中是常见的,并且是许多算法的一部分。
2. 如果你想“节省”空间,并且将多个“bool”变量打包到一个int
中,例如,你为每个bool变量分配一个位,那么位运算符就会经常用到。你必须使用位运算符来能够单独地改变/读取位。
例如,将8个位/bools打包到一个int
中:
flags := 0x00 // 所有标志位都为0
flags |= 0x02 // 将第2位设置为1(其余位保持不变)
flags |= 0xff // 将8个位(0..7)设置为1
flags &= 0xfe // 将最低位设置为0(其余位保持不变)
istrue := flags&0x04 != 0 // 测试第3位是否为1
3. 另一个领域是压缩数据,你希望充分利用一个byte
的所有位来存储/检索一些信息(位是计算和数字通信中的基本信息单位)。
4. 类似于压缩但不完全相同的是位流。它也用于在数据流中节省空间,而不是发送完整的字节,而是发送具有任意位长度的字段。
我编写并发布了一个高度优化的位级读写器包,开源地址在这里:github.com/icza/bitio。你将在其源代码中看到各种位操作的广泛使用。
5. 另一个实际应用是测试(整数)数字的某些属性。通过了解整数数字的二进制表示(二进制补码),可以确定数字在其二进制表示中的某些特征。例如,如果最低位为0,则整数(以二进制补码表示)是偶数(可以被2整除):
func isEven(i int) bool {
return i&0x01 == 0
}
通过测试整数的位,还可以判断它是否是2的幂。例如,如果一个正数只包含一个1
位,那么它是2的幂(例如2 = 0x02 = 00000010b
,16 = 0x10 = 00010000
,但例如17 = 0x11 = 00010001
不是2的幂)。
6. 许多编码/解码过程也使用位运算。最简单的是UTF-8编码,它使用可变长度编码将Unicode代码点(Go中的rune
)表示为字节序列。
可变长度编码的一个简单变体可以使用字节的最高位(第8位或第7位,如果从0开始计数)来表示是否需要更多字节来解码一个数字,而剩下的7位始终是“有用”的数据。你可以测试最高位并像这样“分离”7个有用的位:
b := readOneByte()
usefulBits := b & 0x7f
hasMoreBytes := b & 0x80 != 0
使用这种可变长度编码的好处是,即使在内存中使用了uint64
类型(占用8个字节),小的数字仍然可以使用较少的字节表示(范围在0..127
的数字只需要1个字节!)。如果要存储或传输的样本具有许多小值,仅此就可以将数据压缩到1/8 = 12.5%。缺点是大的数字(在最高字节中具有位)将使用超过8个字节。是否值得取决于样本的启发式算法。
X. 列表还可以继续...
在Go(以及许多其他编程语言)中,如果不了解或不使用位运算符,你是否可以生活下去?答案是可以。但是,如果你了解它们,有时它们可以让你的生活更轻松,使你的程序更高效。
如果你想了解更多关于这个主题的内容,请阅读维基百科文章:位运算,并搜索术语“位运算符教程”,有许多好的文章。
英文:
Bitwise operators come into play when you have to work with byte- or bit-level data.
Here I list a handful of examples using bit operations with code samples (in no particular order):
1. They are common and part of many algorithms in cryptography and hash functions (e.g. MD5).
2. They are also often used if you want to "save" space and you pack multiple "bool" variables into one int
for example, you assign a bit to each bool variable. You have to use bitwise operators to be able to individually change/read the bits.
For example packing 8 bits/bools into one int
:
flags := 0x00 // All flags are 0
flags |= 0x02 // Turn the 2nd bit to 1 (leaving rest unchanged)
flags |= 0xff // Turn 8 bits (0..7) to 1
flags &= 0xfe // Set the lowest bit to 0 (leaving rest unchanged)
istrue := flags&0x04 != 0 // Test if 3rd bit is 1
3. Another area is compressing data where you want to get the most out of a byte
and use all its bits to store/retreive some info (a bit is the basic unit of information in computing and digital communications).
4. Similar to compression but not quite the same: bitstreams. It is also used to save space in a data stream by not sending complete bytes but rather fields having arbitrary bit-length.
I've written and published a highly optimized bit-level Reader and Writer package, open sourced here: github.com/icza/bitio. You will see extensive usage of all kinds of bit operations in its sources.
5. Another practical usage: testing certain properties of an (integer) number. Knowing the binary representation of integer numbers (Two's complement) there are certain characteristics of numbers in their binary representation. For example an integer number (in 2's complement) is even (can be divided by 2) if the lowest bit is 0:
func isEven(i int) bool {
return i&0x01 == 0
}
By testing the bits of an integer you can also tell if it's a power of 2. For example if a positive number only contains one 1
bit, then it is a power of 2 (e.g. 2 = 0x02 = 00000010b
, 16 = 0x10 = 00010000
but for example 17 = 0x11 = 00010001
not power of 2).
6. Many encoding/decoding procedures also use bit operations. The most trivial is the UTF-8 encoding which uses a variable-length encoding for representing unicode code points (rune
in Go) as byte sequences.
A simple variation of a variable-length encoding could be to use the highest bit of a byte (8th or 7th if 0-indexed) to signal if more bytes are required to decode a number, and the remaining 7 bits are always the "useful" data. You can test the highest bit and "separate" the 7 useful bits like this:
b := readOneByte()
usefulBits := b & 0x7f
hasMoreBytes := b & 0x80 != 0
The profit of using such a variable-length encoding is that even if you use uint64
type in Go which is 8 bytes in memory, small numbers can still be represented using less bytes (numbers in the range 0..127
only require 1 byte!). If the samples you want to store or transfer have many small values, this alone can compress the data to 1/8th = 12.5 %. The down side is that big numbers (which have bits even in the highest byte) will use more than 8 bytes. Whether it's worth it depends on the heuristic of the samples.
X. And the list goes on...
Can you live without knowing/using bitwise operators in Go (and in many other programming languages)? The answer is Yes. But if you know them, sometimes they can make your life easier and your programs more efficient.
If you want to learn more on the topic, read the Wikipedia article: Bitwise operation and google the term "Bitwise Operators Tutorial", there are many good articles.
答案2
得分: 23
对于它们的技术操作,请查看此处的注释:
package main
import "fmt"
func main() {
// 使用按位或 | 获取在1或2中的位
// 1 = 00000001
// 2 = 00000010
// 1 | 2 = 00000011 = 3
fmt.Println(1 | 2)
// 使用按位或 | 获取在1或5中的位
// 1 = 00000001
// 5 = 00000101
// 1 | 5 = 00000101 = 5
fmt.Println(1 | 5)
// 使用按位异或 ^ 获取在3或6中的位,但不包括两者都有的位
// 3 = 00000011
// 6 = 00000110
// 3 ^ 6 = 00000101 = 5
fmt.Println(3 ^ 6)
// 使用按位与 & 获取在3和6中的位
// 3 = 00000011
// 6 = 00000110
// 3 & 6 = 00000010 = 2
fmt.Println(3 & 6)
// 使用按位清除与非 &^ 获取在3中但不在6中的位(顺序很重要)
// 3 = 00000011
// 6 = 00000110
// 3 &^ 6 = 00000001 = 1
fmt.Println(3 &^ 6)
}
请注意,我给出了两个 |
的示例,以显示它与 1 + 5
不同,不是简单的加法。
至于实际用途,我相信其他人可以提供更多示例,但一个常见的用途是创建用于权限系统等的标志位掩码。
英文:
For what they technically do check out the comments in this
package main
import "fmt"
func main() {
// Use bitwise OR | to get the bits that are in 1 OR 2
// 1 = 00000001
// 2 = 00000010
// 1 | 2 = 00000011 = 3
fmt.Println(1 | 2)
// Use bitwise OR | to get the bits that are in 1 OR 5
// 1 = 00000001
// 5 = 00000101
// 1 | 5 = 00000101 = 5
fmt.Println(1 | 5)
// Use bitwise XOR ^ to get the bits that are in 3 OR 6 BUT NOT BOTH
// 3 = 00000011
// 6 = 00000110
// 3 ^ 6 = 00000101 = 5
fmt.Println(3 ^ 6)
// Use bitwise AND & to get the bits that are in 3 AND 6
// 3 = 00000011
// 6 = 00000110
// 3 & 6 = 00000010 = 2
fmt.Println(3 & 6)
// Use bit clear AND NOT &^ to get the bits that are in 3 AND NOT 6 (order matters)
// 3 = 00000011
// 6 = 00000110
// 3 &^ 6 = 00000001 = 1
fmt.Println(3 &^ 6)
}
<kbd>View it on the playground</kbd>
Please note that I gave two examples of |
to show that it's not really addition like 1 + 5
.
As for practical uses I'm sure some others could comment with more examples but one common use is to create a bitmask of flags for something like a permission system.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论