Bit Shifting

Shifting moves every bit k places: x << k multiplies by 2ᵏ, x >> k divides. Heap indexing, hashing, and fixed-point maths all lean on shifts.

Category
Bit Manipulation
Time complexity
O(1)
Space complexity
O(1)

Pseudocode

x << 1 doubles
x >> 1 halves
fast ×2ᵏ and ÷2ᵏ

Reference implementation

x &lt;&lt; k  # x · 2^k
x &gt;&gt; k  # x ÷ 2^k
# heap children: 2i+1 = (i&lt;&lt;1)|1

Open the interactive Bit Shifting visualisation →