Search⌘ K
Home
Courses
Grokking Bit Manipulation for Coding Interviews

Solution Review: Get First Set Bit Position

Explore how to find the first set bit position in a number using bitwise left shift and AND operations. Understand the logic and algorithm to identify the rightmost set bit efficiently, with a constant time complexity solution ideal for coding interviews.

We'll cover the following...

Solution review

Imagine we check the right-most significant bit to see if the bit and & operation of 1 yields to 1.

In other words, we shift bits until the right MSB and & operation with 1, and it yields 1.

Algorithm

  • If n == 0, return.
  • Initialize k = 1
  • Loop
    • If ((n & (1 << (k -
...