tags : Algorithms, Data Structures
FAQ
Why bitshift and have data structures in base2?
- using powers of 2 allows the use of cheap bit masks
- shifts are cheaper than expensive division
Resources
Basics
Positional notation
Multiplying (Left shift <<)
- 1 << 8 = 1 << 23 = 256 = 1 shifted by 8 bits to left
Division (Right shift >>)
- 40 >> 1 = 40 >> 20 = 20 = 40 divided by 21
- 40 >> 2 = 40 >> 21 = 10 = 40 divided by 22
- 36 >> 2 = 36 >> 21 = 09 = 36 divided by 22
- 1024 >> 8 = 1024 >> 23 = 4 = 1024 divided by 28
Logical and arithmetic shifts
- Arithmetic : Respect the sign bit (
>>/<<) - Logical : Do not respect the sign bit (
>>>/<<<) - In Java you can explicitly tell which one to use, in Cpp or Golang, implementations choose shift to perform depending on the type of integer being shifted.
- Signed integers are shifted using the arithmetic shift.
- Unsigned integers are shifted using the logical shift.