Hacker News new | ask | show | jobs
by philshem 568 days ago
Could explain the << calculation a bit? I read about the operator but it’s not clear how this works
3 comments

It means "left shift" in binary. This corresponds to adding a specified number of zeros at the end of the binary representation of the original number. So 1 << 0 is binary 1, 1 << 1 is binary 10, 1 << 2 is binary 100, 1 << 3 is binary 1000...

If you think about the meaning of place value in binary, this is exactly the same as raising two to a specified power. Each time you shift one place further left in binary, it's equivalent to multiplying the existing number by two. So repeating that a specified number of times is multiplying by a specified power of two.

1 is 2 to the power 0 ... 0b0001

shifted left once, it becomes 2 to the power 1 ... 0b0010

shifted left twice, it becomes 2 to the power 2 ... 0b0100

shifted left three times, it becomes 2 to the power 3 ... 0b1000

etc until

shifted left 136_279_841 times, it becomes 2 to the power 136_279_84 ... 0b1000...many zeros...0000

subtract 1, it becomes

0b0111...many ones...1111

One funny thing about Mersenne primes is that, as a result of what you describe, they are exactly those primes whose binary representation consists of a prime number of ones!

The smallest Mersenne prime, three, is binary 11, while the next largest is seven (111), then 31 (11111), then 127 (1111111). The next candidate, 2047 (11111111111), is not prime.

Shifting an integer left `n` bits is equivalent to multiplying it by `2 ** n`