这个问题解释了用于计算给定数字中1个数的SWAR算法。在解释ilmari写道0x01010101=(1<<24)+(1<<16)+(1<<8)+1。有人能解释一下它是如何平等的吗。
您首先需要了解<<
运算符的作用。它执行向左的逐位移位。让我们采用0b
前缀表示二进制符号,0x
前缀表示十六进制符号:
1 << 8 = 0b100000000 = 256 = 0x100
类似:
1 << 16 = 0b10000000000000000 = 65536 = 0x10000
因此:
(1 << 8) + (1 << 16) = 0x10100
通过将(1 << 24)
和1
相加,您将得到最终结果:0x01010101
。
请注意,虽然它看起来非常像二进制值,但它是十六进制值。如果我们把它写成二进制,我们得到:
0b1000000010000000100000001
^ ^ ^ ^
bit #24 bit #16 bit #8 bit #0
1 0000 0000 0000 0000 0000 0000 Shifting 1 left by 24 places
1 0000 0000 0000 0000 Shifting 1 left by 16 places
1 0000 0000 Shifting 1 left by 8 places
1
================================
1 0000 0001 0000 0001 0000 0001 Result after adding
即0x01010101。
让我们从总数开始:
Hex: 0x01010101
Decimal: 16843009
Binary: 1000000010000000100000001
现在单独来看它们。从1 << 24
开始(也就是左移24次的1,也就是24个零的二进制1):
Calculation: 1 << 24
Decimal: 16777216
Binary: 1000000000000000000000000
// ^ 25th position because 1 was shifted 24 times to the left
Calculation: 1 << 16
Decimal: 65536
Binary: 0000000010000000000000000
// ^ 17th position because 1 was shifted 16 times to the left
Calculation: 1 << 8
Decimal: 256
Binary: 0000000000000000100000000
// ^ 9th position because 1 was shifted 8 times to the left
1是显而易见的,所以我不包括它。现在把它们加在一起:
1000000000000000000000000 = 1 << 24
0000000010000000000000000 = 1 << 16
0000000000000000100000000 = 1 << 8
+ 0000000000000000000000001 = 1
|-------|-------|-------|
1000000010000000100000001 = 16843009
然后我们回到开头,十六进制中的16843009
是0x01010101
。