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.