Remove Rightmost Set Bit in Binary Representation.

Problem Statement: Given a number n, remove its rightmost set bit (i.e., the lowest bit that is set to 1) and return the updated number.

Example 1:
Input: n = 18
Binary: 10010
Output: 16
Explanation: 18 & 17 = 10010 & 10001 = 10000 (16)

Example 2:
Input: n = 40
Binary: 101000
Output: 32
Explanation: 40 & 39 = 101000 & 100111 = 100000 (32)

Approach:

The binary representation of a number contains bits (0s and 1s). A set bit is a bit with value 1. The rightmost set bit is the lowest 1 when scanning from right to left.

To remove this bit, we use the trick:

n & (n - 1)

Why n & (n - 1) work?

Let’s say:

• n = xxx1000 (where the rightmost set bit is the last 1 before a string of zeros)
• n - 1 = xxx0111 (it flips all bits from that position)

When you AND these two:

• All bits after the rightmost 1 become 0
• The rightmost 1 is turned to 0
• All other bits remain the same

Example:

18 & (18 - 1)  
= 10010 & 10001  
= 10000  
= 16 (in decimal)

Example Code:

        
#include <iostream>
using namespace std;

int removeRightmostSetBit(int n) {
    return n & (n - 1);
}

int main() {
    int n = 18;
    cout << "After removing rightmost set bit: " << removeRightmostSetBit(n) << endl;
    return 0;
}

        

        
# Python Example to Remove the Rightmost Set Bit
def remove_rightmost_set_bit(n):
    return n & (n - 1)

n = 18
print("After removing rightmost set bit:", remove_rightmost_set_bit(n))

        

        
// Java Example to Remove the Rightmost Set Bit
public class RemoveRightmostSetBit {
    public static int removeRightmostSetBit(int n) {
        return n & (n - 1);
    }

    public static void main(String[] args) {
        int n = 18;
        System.out.println("After removing rightmost set bit: " + removeRightmostSetBit(n));
    }
}

        

Output:

After removing rightmost set bit: 16

Using n & (n - 1) is a powerful bitwise trick to remove the rightmost set bit efficiently in constant time. It's widely used in many algorithmic problems and is a must-know technique for interviews and competitive programming.

Check Whether the Last Bit is a Set Bit or Not.

While solving Bit Manipulation, we sometimes use several tricks, and one such trick that we are going to discuss here is how to check if the last bit of any given number is set or not. It is an easy one-line trick, but used to solve many Bit Manipulation-related problems. One such popular example is finding if a number is even or odd using Bit Manipulation. 

Let's first understand the problem statement, and then we will understand the trick with a few examples.

Example:

Input: n = 13
Output: true
Explanation:
n = 13 = 1101
As the last bit is set bit so return true.

Input: n = 8
Output: false
Explanation:
n = 8 = 1000
As the last bit is not set bit so return false. 

Approach.

To check whether the last bit of a number is set, we perform a bitwise AND operation between the number and 1 (i.e., n & 1). This operation isolates the least significant bit. If the result is 1, the last bit is set; if it's 0, the last bit is not set. Let's understand the approach with a few examples:

Let's say n = 13.

So the binary representation of 13 is 1101. 

As we want to perform an AND operation between n and 1, so binary representation of 1 is 0001.

1101 & 0001 = 0001 = 1, as the AND operation returns a set bit only if both bits are set.

We will get 1 in our result only if the last bit of the given number is a set bit, else it will always result in 0.

Example Code:

        
// Example C++: Check if last bit is Set bit
#include <iostream>
using namespace std;

void checkLastBit(int n) {
    if (n & 1)
        cout << "Last bit is set (1)" << endl;
    else
        cout << "Last bit is not set (0)" << endl;
}

int main() {
    int n;
    cout << "Enter a number: ";
    cin >> n;

    checkLastBit(n);

    return 0;
}

        

        
# Example Python: Check if last bit is Set bit
def check_last_bit(n):
    if n & 1:
        print("Last bit is set (1)")
    else:
        print("Last bit is not set (0)")

n = int(input("Enter a number: "))
check_last_bit(n)

        

        
// Example Java: Check if last bit is Set bit
import java.util.Scanner;

public class LastBitChecker {

    public static void checkLastBit(int n) {
        if ((n & 1) == 1) {
            System.out.println("Last bit is set (1)");
        } else {
            System.out.println("Last bit is not set (0)");
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter a number: ");
        int n = scanner.nextInt();

        checkLastBit(n);
    }
}
       

Output:

Enter a number: 13

Last bit is set (1)

This is one of the most commonly used micro-optimizations in competitive programming and interviews

Find Wether a Given Number is Power of 2.

Determining if a number is a power of 2 is a common problem in computer science and programming. A number is considered a power of 2 if it can be expressed as 2^n, where n is a non-negative integer. For example, the numbers 1, 2, 4, 8, 16, and so on are all powers of 2.

In this post, we will explore two approaches to solve this problem: the normal approach and the bitwise approach.

Problem: Given an integer n, determine whether it is a power of two.

Example:

Input:  8  
Output: true  
Explanation: 8 = 2^3 → It is a power of 2

Input:  6  
Output: false  
Explanation: 6 is not a power of 2

Approach 1: Brute Force Loop.

Keep dividing the number by 2. If at the end, you reach 1, then it's a power of 2.

If at any point, it's not divisible by 2, return false.

Steps:

• If n == 0, return false
• While n % 2 == 0, divide n by 2
• If n == 1 after loop → power of 2

Example Code:

        
// C++ Example: Find Power of 2
#include <iostream>
using namespace std;

bool isPowerOfTwoLoop(int n) {
    if (n <= 0) return false; 
    while (n % 2 == 0) { 
        n = n / 2; 
    }
    return n == 1; 
}

int main() {
    int number;
    cout << "Enter a number: ";
    cin >> number;

    if (isPowerOfTwoLoop(number)) {
        cout << number << " is a power of 2." << endl;
    } else {
        cout << number << " is not a power of 2." << endl;
    }

    return 0;
}

        

        
#Python Example: Find Power of 2
def is_power_of_two_loop(n: int) -> bool:
    if n <= 0:
        return False
    while n % 2 == 0:
        n = n // 2
    return n == 1

# Example usage
if __name__ == "__main__":
    number = int(input("Enter a number: "))
    if is_power_of_two_loop(number):
        print(f"{number} is a power of 2.")
    else:
        print(f"{number} is not a power of 2.")

        

        
//Java Example: Find Power of 2
import java.util.Scanner;

public class PowerOfTwo {
    public static boolean isPowerOfTwoLoop(int n) {
        if (n <= 0) return false;
        while (n % 2 == 0) {
            n = n / 2;
        }
        return n == 1;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter a number: ");
        int number = scanner.nextInt();

        if (isPowerOfTwoLoop(number)) {
            System.out.println(number + " is a power of 2.");
        } else {
            System.out.println(number + " is not a power of 2.");
        }

        scanner.close();
    }
}

        

Output:

8 is a power of 2.

• Time Complexity: O(log n)
• Space Complexity: O(1)

Approach 2: Bit Manipulation Approach.

A number is a power of two if it can be expressed as 2^n, where n is a non-negative integer. In binary representation, powers of two have a unique property: they have exactly one bit set to 1. 

For example:

1  = 0001   → 2^0  

2  = 0010   → 2^1  

4  = 0100   → 2^2  

8  = 1000   → 2^3  

16 = 10000  → 2^4  

This property allows us to efficiently check if a number is a power of two using bit manipulation.

To determine if a number n is a power of two using bit manipulation, we can use the following approach:

1. Check if n is greater than zero: Powers of two are positive numbers.

2. Use the expression (n&(n-1): This expression will be zero if n is a power of two. The reason behind this is that subtracting 1 from a power of two flips all the bits after the rightmost set bit (the only 1 in the binary representation). For example:

• For n = 4 (0100), n-1 = 3 (0011)
• The bitwise AND operation: 0100 & 0011 = 0000

Now, let's implement this logic in C++, Python, and Java.

Example Code:

        
#include <iostream>

bool isPowerOfTwo(int n) {
    return (n > 0) && ((n & (n - 1)) == 0);
}

int main() {
    int number = 8;
    if (isPowerOfTwo(number)) {
        std::cout << number << " is a power of two." << std::endl;
    } else {
        std::cout << number << " is not a power of two." << std::endl;
    }
    return 0;
}

        

        
# Find Wether a number is Power of 2 Using Bitwise Operator
def is_power_of_two(n):
    return n > 0 and (n & (n - 1)) == 0

number = 8
if is_power_of_two(number):
    print(f"{number} is a power of two.")
else:
    print(f"{number} is not a power of two.")

        

        
// Java Code to Find if a number is power of 2 using bitwise Operator
public class PowerOfTwo {
    public static boolean isPowerOfTwo(int n) {
        return n > 0 && (n & (n - 1)) == 0;
    }

    public static void main(String[] args) {
        int number = 8;
        if (isPowerOfTwo(number)) {
            System.out.println(number + " is a power of two.");
        } else {
            System.out.println(number + " is not a power of two.");
        }
    }
}        

Output:

8 is a power of two.

• Time Complexity: O(l)
• Space Complexity: O(1)

Find If a Number is Even or Odd Using Bitwise Operator.

Understanding whether a number is even or odd is one of the most common tasks in programming. While most beginners use the arithmetic modulus operator (%), there’s a faster and more efficient alternative the bitwise AND operator (&).

In this post, we'll explore both approaches, compare them, and understand why bitwise is better.

Approach 1: Using Arithmetic Operator.

The most common and straightforward method is using the modulus operator (%). If a number divided by 2 leaves a remainder of 0, it's even. Otherwise, it's odd.

if (n % 2 == 0) → Even  
else → Odd

Example Code:

// C++ Example: Find Number is Odd or Even
#include <iostream>
using namespace std;

void checkEvenOrOdd_Arithmetic(int n) {
    if (n % 2 == 0)
        cout << n << " is Even" << endl;
    else
        cout << n << " is Odd" << endl;
}
        

# Python Example: Find Number is Even or Odd
def check_even_or_odd_arithmetic(n):
    if n % 2 == 0:
        print(f"{n} is Even")
    else:
        print(f"{n} is Odd")
        

// Java Example: Find Number is Even or Odd
public class CheckEvenOrOdd {
    public static void checkEvenOrOddArithmetic(int n) {
        if (n % 2 == 0) {
            System.out.println(n + " is Even");
        } else {
            System.out.println(n + " is Odd");
        }
    }

    public static void main(String[] args) {
        // Example usage
        int number = 10;
        checkEvenOrOddArithmetic(number);
    }
}
        

Output:

6 is Even

Approach 2: Using Bitwise AND Operator.

A faster and smarter way to check if a number is even or odd is using bitwise operators.

The & operator performs a bit-by-bit comparison between two numbers.

For each bit, it returns:

• 1 if both bits are 1
• 0 otherwise

When you perform n & 1, you're checking the Least Significant Bit (LSB) of the number.

• If LSB is 0 → number is even
• If LSB is 1 → number is odd

Because the binary of even number always end with 0 and binary of odd number always end with 1. Let's understand this with few examples:

Example 1: 

Number = 4
Binary of 4: 0100
Binary of 1: 0001

    0100
AND 0001
  = 0000 → 0 → Even

Example 2:

Number = 7
Binary of 7: 0111
Binary of 1: 0001

    0111
AND 0001
  = 0001 → 1 → Odd

Example Code:

        
//C++ Example: Find Even and Odd Using Bitwise AND
#include <iostream>
using namespace std;

void checkEvenOrOdd_Bitwise(int n) {
    if (n & 1)
        cout << n << " is Odd" << endl;
    else
        cout << n << " is Even" << endl;
}

int main() {
    checkEvenOrOdd_Bitwise(4);
    return 0;
}

        

        
#Python Example: Find Even and Odd Using def check_even_or_odd_bitwise(n):
    if n & 1:
        print(f"{n} is Odd")
    else:
        print(f"{n} is Even")

# Example usage
if __name__ == "__main__":
    check_even_or_odd_bitwise(4)


        

        
//Java Example: Find Even and Odd Using Bitwise AND
public class CheckEvenOrOddBitwise {
    public static void checkEvenOrOddBitwise(int n) {
        if ((n & 1) == 1) {
            System.out.println(n + " is Odd");
        } else {
            System.out.println(n + " is Even");
        }
    }

    public static void main(String[] args) {
        checkEvenOrOddBitwise(4);
    }
}

        

Output:

6 is Even

Using n & 1 is a fast and efficient way to check if a number is even or odd by examining its last binary bit. It's a foundational concept in bit manipulation that helps build strong binary thinking.

 

Bit Manipulation Introduction.

Bit Manipulation is one of the most powerful and efficient techniques in programming. It involves working directly with binary digits (0s and 1s) using special operators called bitwise operators.

You may not realize it, but every number in your computer is stored in binary, and by manipulating these bits smartly, you can solve many problems faster and with less memory.

In this article, we’ll break down what bits are, how to convert between decimal and binary, and how to use bitwise operators with simple examples. We’ll also explain the concept of 2’s complement, which is used to represent negative numbers in binary.

What is a Bit?

A bit (short for binary digit) is the smallest unit of data in a computer. It can have only two possible values:

• 0 (OFF)
• 1 (ON)

All information in a computer — numbers, characters, images — is stored using bits. Multiple bits are grouped together to represent more complex data. For example:

• 1 Byte = 8 bits
• 5 in binary (8-bit) = 00000101

What is Bit Manipulation?

Bit Manipulation is a programming technique that involves working directly with the individual bits (0s and 1s) of a number using special operators called bitwise operators.

In simple terms, it's a way to perform fast and efficient operations by changing or checking the binary form of numbers — the language that computers understand best.

Bit manipulation helps in:

• Optimizing performance
• Saving memory using bit flags or masks
• Solving mathematical and logical problems more efficiently

It’s widely used in competitive programming, system-level code, and interview problem-solving.

Before diving into bit manipulation techniques, it’s important to understand how numbers are represented in binary form. Since bit manipulation deals with binary digits (bits) directly, knowing how to convert between decimal and binary is the foundation.

Decimal to Binary Conversion.

To convert a decimal number to binary, we use repeated division by 2.

Steps:

• Divide the number by 2.
• Record the remainder (it will be 0 or 1).
• Continue dividing the quotient by 2 until it becomes 0.
• The binary number is the reverse order of the remainders.

Example: Convert 13 to Binary

13 ÷ 2 = 6 remainder 1  
6 ÷ 2 = 3 remainder 0  
3 ÷ 2 = 1 remainder 1  
1 ÷ 2 = 0 remainder 1

→ Binary = 1101

So, 13 in binary is 1101.

Binary to Decimal Conversion

To convert a binary number to decimal, we multiply each bit by 2 raised to the power of its position (starting from the right, index 0).

Steps:

• Start from the rightmost bit.
• Multiply each bit by 2^position.
• Sum all the results.

Example: Convert 1010 to Decimal

= 1×2³ + 0×2² + 1×2¹ + 0×2⁰  
= 8 + 0 + 2 + 0  
= 10

So, 1010 in binary is 10 in decimal.

Now that you know how to convert a decimal number to binary and how to represent numbers in binary form, it's the right time to understand Bitwise Operators.

Bitwise Operators.

Bitwise operators allow us to directly manipulate individual bits of binary numbers. These operators form the backbone of bit manipulation techniques used in coding problems and optimization.

Let’s explore each bitwise operator with simple examples.

1. Bitwise AND (&)- The AND operator compares two bits and returns 1 only if both bits are 1; otherwise, it returns 0.

Truth Table of Bitwise AND

A	B	A & B
0	0	0
0	1	0
1	0	0
1	1	1

Example:

5 = 0101  
3 = 0011  
5 & 3 = 0001 → 1

2. Bitwise OR (|)- The OR operator returns 1 if at least one of the bits is 1.

Truth Table of Bitwise OR

A	B	A | B
0	0	0
0	1	1
1	0	1
1	1	1

Example:

5 = 0101  
3 = 0011  
5 | 3 = 0111 → 7

3. Bitwise XOR (^)- The XOR (exclusive OR) operator returns 1 only if the two bits are different.

Truth Table of Bitwise XOR

A	B	A ^ B
0	0	0
0	1	1
1	0	1
1	1	0

Example:

5 = 0101  
3 = 0011  
5 ^ 3 = 0110 → 6

4. Bitwise NOT (~)- The NOT operator flips each bit:

• 0 becomes 1
• 1 becomes 0

However, in most programming languages (like C++, Java, Python), numbers are stored in 2’s complement format, so applying ~ to a number results in -(n + 1). At the end of this article, we have explained 2's Complement in detail.

Example:

~5 = -(5 + 1) = -6

Let's break it down:

5   = 00000101  
~5  = 11111010 (in 8-bit) → which is -6 in 2’s complement

5. Left Shift (<<)- The left shift operator shifts bits to the left by a given number of positions. Each left shift is equivalent to multiplying the number by 2^n.

Example:

5 << 1 = 10  
Binary: 0101 << 1 → 1010

6. Right Shift (>>)- The right shift operator shifts bits to the right. Each right shift divides the number by 2^n, ignoring the remainder.

Example:

5 >> 1 = 2  
Binary: 0101 >> 1 → 0010

That's all about the Bitwise Operators that we will use to solve problems using bit manipulation.

Let's understand one last topic of in introduction part, and that is 2's Complement. Many times, learners find it difficult to understand this and their use.

What is 2's Complement?

2’s Complement is a method used by computers to represent negative numbers in binary form. It allows addition, subtraction, and other operations to work seamlessly with both positive and negative integers using the same circuitry.

How to Find 2’s Complement?

To find the 2’s complement of a positive number:

• Write the number in binary (fixed width, e.g., 8 bits).
• Invert all the bits (change 0 to 1 and 1 to 0).
• Add 1 to the result.

With 2’s complement:

• Positive numbers start from 00000000 (0) to 01111111 (+127)
• Negative numbers start from 11111111 (–1) to 10000000 (–128)

Example: Find the 2’s Complement of 5

Step 1: Binary of 5 in 8 bits = 00000101
Step 2: Invert bits → 11111010
Step 3: Add 1 → 11111011

Result: 11111011 is -5 in 2’s complement form.

Now I hope you have understood all the topics that we have discussed in this post, and are ready to solve real-life problems.

Bit manipulation is a powerful concept that allows you to write faster and more memory-efficient programs. By mastering binary conversions and bitwise operators, you unlock the ability to solve a wide range of DSA problems more effectively.

Convert Binary Linked List to Integer.

Given a Singly Linked List containing n nodes, each node of the list can hold either 0 or 1 and the most significant bit is present at the head of the linked list. The entire linked list is a binary representation of a decimal number. Return the decimal value represented by the given binary linked list. 

Note: The linked list is not empty and the maximum number of nodes will be less than 30.

Example 1: 
Input: 1->0->1->1
Output: 11

Example 2:
Input: 1->0->1
Output: 5

Approach 1: Converting Binary Using Arithmetic calculation.

You can solve this problem by diving the problem into two sub-problems:

• Find the number of binary digits present in the given linked list that is needed for the arithmetic calculation.
• Convert the Binary to a Decimal number using classic arithmetic calculation (see the above image).

C++ Solution Code:

//C++ Program to convert Binary Linked List to Decimal
#include<bits/stdc++.h>
using namespace std;

class ListNode{
    public:
      int data;
      ListNode *next;

    //constructor
    ListNode(int data){
        this->data = data;
        this->next = NULL;
    }  
};
//creating new node
ListNode *newNode(int data){
    ListNode *temp = new ListNode(data);
    temp->next = NULL;
    return temp;
}
//function to find length of linked list
int listLength(ListNode* head){
    ListNode *temp = head;
    int len = 0;
    while(temp != NULL){
        temp = temp->next;
        len++;
    }
    return len;
}
//function to convert binary to decimal
int getDecimalValue(ListNode *head){
    
    int len = listLength(head);
    int ans = 0;
    ListNode *temp = head;
    int i = 1;

    while(temp != NULL){
        int res = (temp->data)*pow(2, len-i);
        temp = temp->next;
        i++;
        ans += res;
    }
    return ans;
}
int main(){
    ListNode *head = newNode(1);
    head->next = newNode(0);
    head->next->next = newNode(1);

    cout<<"Integer Value: "<<getDecimalValue(head);

    return 0;
}

Output:

Integer Value: 5

• Time Complexity: O(n)
• Space Complexity: O(1)

Approach 2: Using Bit Manipulation.

In this approach, bit manipulation technique in which we will traverse the linked list starting from head till end. Updating the current value with head->next->value. Updating the result by shifting the digit by one to the left and performing logical OR with current vlaue.

C++ Solution code:

/*C++ Program to convert Binary Linked List to Decimal
Using bit manipulation*/
#include<bits/stdc++.h>
using namespace std;

class ListNode{
    public:
      int data;
      ListNode *next;

    //constructor
    ListNode(int data){
        this->data = data;
        this->next = NULL;
    }  
};
//creating new node
ListNode *newNode(int data){
    ListNode *temp = new ListNode(data);
    temp->next = NULL;
    return temp;
}

//function to convert binary to decimal
int getDecimalValue(ListNode *head){
    
    int num = head->data;
    while (head->next != NULL)
    {
        num = (num << 1) | head->next->data;
        head = head->next;
    }
    
    return num;
}
int main(){
    ListNode *head = newNode(1);
    head->next = newNode(0);
    head->next->next = newNode(1);

    cout<<"Integer Value: "<<getDecimalValue(head);

    return 0;
}

Output:

Integer Value: 5

• Time Complexity: O(n)
• Space Complexity: O(1)

Related Articles:

• Find the Middle of the Singly Linked List in C++.

• Reverse a Singly Linked List in C++.

• Merge Two Sorted Linked List in C++.

• Intersection Point of Two Linked Lists in C++.

• Detect Cycle in a Linked List in C++.