How 0x01010101 is equivalent to 1<<24 + 1<<16 + 1<<8 + 1

Question

This question gives explanation about SWAR algorithm used for counting number of 1s in a given number. While explaining ilmari wrote 0x01010101 = (1 << 24) + (1 << 16) + (1 << 8) + 1. Can someone explain how it is equal.

Answer 1

You'll first need to understand what the << operator is doing. It performs a bitwise shift to the left. Let's adopt the 0b prefix for binary notation and 0x for hexadecimal notation:

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

Similarly:

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

So:

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

By adding (1 << 24) and 1, you'll get the final result: 0x01010101.

Please note that while it looks an awful lot like a binary value, it is a hexadecimal one. If we write it as binary, we get:

 0b1000000010000000100000001
   ^       ^       ^       ^
bit #24 bit #16  bit #8  bit #0

Answer 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

I.e. 0x01010101.

Answer 3

Let's start with the total number:

Hex:     0x01010101
Decimal: 16843009
Binary:  1000000010000000100000001

Now look at them individually. Start with 1 << 24 (aka. 1 left shifted 24 times, aka. a binary 1 with 24 zeroes):

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 is obvious, so I won't include that. Now add them all together:

  1000000000000000000000000 = 1 << 24
  0000000010000000000000000 = 1 << 16
  0000000000000000100000000 = 1 << 8
+ 0000000000000000000000001 = 1
  |-------|-------|-------|
  1000000010000000100000001 = 16843009

And then we're back at the start, 16843009 in hex is 0x01010101.