Last Set Bit

The last set bit, also known as the least significant 1 bit, refers to finding the position of the rightmost 1 in the binary representation of a number. Bitwise operators can compute this efficiently.

Java example:

1
2
3
4
5
6
7

int lastSetBit(int n) {
  return log2(n & -n) + 1;
}

int log2(int n) {
  return 31 - Integer.numberOfLeadingZeros(n); 
}

C++ example:

1
2
3
4
5
6
7

int lastSetBit(int n) {
  return log2(n & -n) + 1;  
}

int log2(int n) {
  return 31 - __builtin_clz(n);
} 

Python example:

1
2

def last_set_bit(n):
  return (n & -n).bit_length() - 1

The key steps are:

• Use bitwise AND with two’s complement to clear all bits after the last set bit
• Compute the log2 or bit length to find the position

The last set bit operation is useful for many bit-level algorithms and optimizations.

The Last Set Bit refers to the rightmost bit that is set to ‘1’ in the binary representation of a number. It plays a crucial role in many computer algorithms, such as those used for compression, cryptography, and network routing. Knowing the position of the last set bit can provide insights into the structure of the data.

Example Code

Java

In Java, you can find the position of the last set bit using bitwise operations and loops.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

public class Main {
  public static int findLastSetBit(int n) {
    int position = 1;
    while ((n & 1) == 0) {
      position++;
      n >>= 1;
    }
    return position;
  }

  public static void main(String[] args) {
    int num = 20;  // Binary: 10100
    int lastSetBit = findLastSetBit(num);
    System.out.println("Last Set Bit Position: " + lastSetBit);  // Output: 3
  }
}

• n >>= 1: Right-shifts the bits of n to loop through each bit.
• (n & 1) == 0: Checks if the rightmost bit is 0.

C++

C++ code to find the last set bit is quite similar to Java.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

#include <iostream>
using namespace std;

int findLastSetBit(int n) {
  int position = 1;
  while ((n & 1) == 0) {
    position++;
    n >>= 1;
  }
  return position;
}

int main() {
  int num = 20;  // Binary: 10100
  int lastSetBit = findLastSetBit(num);
  cout << "Last Set Bit Position: " << lastSetBit << endl;  // Output: 3
}

• n >>= 1: Right-shifts the bits.
• (n & 1) == 0: Checks the last bit.

Python

Python offers a simple way to find the last set bit as well.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def find_last_set_bit(n):
  position = 1
  while (n & 1) == 0:
    position += 1
    n >>= 1
  return position

num = 20  // Binary: 10100
last_set_bit = find_last_set_bit(num)
print(f"Last Set Bit Position: {last_set_bit}")  // Output: 3

• n >>= 1: Right-shifts the bits of n.
• (n & 1) == 0: Checks the last bit.

Key Takeaways

• The Last Set Bit is the rightmost ‘1’ in the binary representation of a number.
• The operation involves bitwise right-shifting and bitwise AND to identify the last set bit.
• The method to find the last set bit is consistent across Java, C++, and Python.