0

这个问题解释了用于计算给定数字中 1 的数量的SWAR 算法。在解释ilmari 时写道 0x01010101 = (1 << 24) + (1 << 16) + (1 << 8) + 1。有人可以解释它是如何平等的。

4

3 回答 3

3

您首先需要了解<<操作员在做什么。它执行向左移位。让我们采用0b二进制表示法和十六进制表示法的前缀0x：

1 << 8 = 0b100000000 = 256 = 0x100

相似地：

1 << 16 = 0b10000000000000000 = 65536 = 0x10000

所以：

(1 << 8) + (1 << 16) = 0x10100

通过添加(1 << 24)and 1，您将得到最终结果：0x01010101.

请注意，虽然它看起来很像二进制值，但它是一个十六进制值。如果我们把它写成二进制，我们得到：

 0b1000000010000000100000001
   ^       ^       ^       ^
bit #24 bit #16  bit #8  bit #0
于 2016-08-04T13:08:29.597 回答
2 
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。

于 2016-08-04T13:06:40.470 回答
1

让我们从总数开始：

Hex:     0x01010101
Decimal: 16843009
Binary:  1000000010000000100000001

现在逐个查看它们。从1 << 24（又名 1左移24 次，又名带有 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.

于 2016-08-04T13:08:07.017 回答