Chapter 13: Bit Manipulation

Continuing the journey through Data Structures and Algorithms with Java. In this chapter, we will delve into the fascinating world of bit manipulation—a powerful technique in programming that allows us to perform operations at the binary level. Mastering bit manipulation can lead to more efficient algorithms and a deeper understanding of how data is represented in computers.

1. Introduction to Bit Manipulation

Bit manipulation involves operations that directly manipulate bits or binary digits (0s and 1s). This technique is essential in various applications, such as optimizing space, performing fast calculations, and working with low-level data processing. Understanding bit manipulation allows developers to write efficient code, especially in competitive programming and system-level applications.

2. Binary Number System

The binary number system is the foundation of all computing systems. Unlike the decimal system, which is base 10, the binary system is base 2 and consists only of two digits: 0 and 1. Each digit represents a power of 2, making binary essential for computer architecture and data representation.

3. Bitwise Operators

Bitwise operators are used to perform operations on bits directly. The primary bitwise operators include:

• AND (&): Returns 1 if both bits are 1.

• OR (|): Returns 1 if at least one bit is 1.

• XOR (^): Returns 1 if the bits are different.

• NOT (~): Inverts all bits.

4. Binary AND

The binary AND operator (&) compares each bit of two binary numbers. If both bits are 1, the result is 1; otherwise, it's 0. For example:

   1010 (10)
&  1100 (12)
  ---------
   1000 (8)

5. Binary OR

The binary OR operator (|) compares each bit of two binary numbers. If at least one of the bits is 1, the result is 1. For example:

   1010 (10)
|  1100 (12)
  ---------
   1110 (14)

6. Binary XOR

The binary XOR operator (^) compares two bits and returns 1 if the bits are different. For example:

   1010 (10)
^  1100 (12)
  ---------
   0110 (6)

7. Binary 1's Complement

The 1's complement of a binary number is obtained by flipping all the bits (0s to 1s and vice versa). For instance, the 1's complement of 1010 is 0101.

8. Binary Left Shift

The left shift operator (<<) shifts the bits of a number to the left by a specified number of positions, effectively multiplying the number by 2 for each shift. For example:

   0001 (1)
<< 1
  ---------
   0010 (2)

9. Binary Right Shift

The right shift operator (>>) shifts the bits of a number to the right by a specified number of positions, effectively dividing the number by 2 for each shift. For example:

   0010 (2)
>> 1
  ---------
   0001 (1)

10. Check if Odd or Even

To check if a number is odd or even, we can use the bitwise AND operator. If the least significant bit (LSB) is 1, the number is odd; if it is 0, the number is even:

boolean isOdd(int num) {
    return (num & 1) == 1;
}

11. Get ith Bit

To retrieve the ith bit of a number, we can use the right shift operator along with the AND operator:

int getBit(int num, int i) {
    return (num >> i) & 1;
}

12. Set ith Bit

To set the ith bit to 1, we can use the OR operator:

int setBit(int num, int i) {
    return num | (1 << i);
}

13. Clear ith Bit

To clear the ith bit (set it to 0), we can use the AND operator with a negated bit mask:

int clearBit(int num, int i) {
    return num & ~(1 << i);
}

14. Update ith Bit

To update the ith bit, we first clear it and then set it to the desired value (0 or 1):

int updateBit(int num, int i, int bit) {
    return (num & ~(1 << i)) | (bit << i);
}

15. Clear Last i Bits

To clear the last i bits of a number, we can use a mask:

int clearLastIBits(int num, int i) {
    return num & ~((1 << i) - 1);
}

16. Clear Range of Bits

To clear bits from position i to j, we create a mask that has 0s in the range and 1s elsewhere:

int clearBitsInRange(int num, int i, int j) {
    int allOnes = ~0; // All bits are 1
    int left = allOnes << (j + 1); // 1s before j
    int right = (1 << i) - 1; // 1s after i
    int mask = left | right; // 1s everywhere except the range i to j
    return num & mask; // Clear the bits
}

17. Check if a Number is a Power of 2

A number is a power of 2 if it has exactly one bit set. We can check this using the following condition:

boolean isPowerOfTwo(int num) {
    return num > 0 && (num & (num - 1)) == 0;
}

18. Count Set Bits in a Number

To count the number of set bits (1s) in a binary representation of a number, we can use the following approach:

int countSetBits(int num) {
    int count = 0;
    while (num > 0) {
        count += (num & 1);
        num >>= 1;
    }
    return count;
}

19. Fast Exponentiation

Fast exponentiation allows us to compute powers in logarithmic time. The basic idea is to use the properties of exponents:

int fastExponentiation(int base, int exp) {
    int result = 1;
    while (exp > 0) {
        if ((exp & 1) == 1) { // If exp is odd
            result *= base;
        }
        base *= base; // Square the base
        exp >>= 1; // Divide exp by 2
    }
    return result;
}

20. Fast Exponentiation Code

Here’s a complete Java function implementing fast exponentiation:

public class BitManipulation {
    public static void main(String[] args) {
        int base = 2;
        int exp = 10;
        int result = fastExponentiation(base, exp);
        System.out.println(base + "^" + exp + " = " + result);
    }

    static int fastExponentiation(int base, int exp) {
        int result = 1;
        while (exp > 0) {
            if ((exp & 1) == 1) {
                result *= base;
            }
            base *= base;
            exp >>= 1;
        }
        return result;
    }
}

Assignment

1. Implement functions for each of the bit manipulation concepts discussed in this chapter.

2. Create a test suite to validate the correctness of your implementations.

3. Solve the following problems using bit manipulation:

   • Find the unique number in an array where every other number appears twice.

   • Reverse the bits of a given integer.

   • Find the two non-repeating elements in an array where every other element repeats twice.

By mastering bit manipulation, you will greatly enhance your ability to tackle various algorithmic challenges efficiently. Keep practicing, and happy coding!

Related Posts in My Series:

DSA in Java Series:

• Chapter 2: Operators in Java – Learn about the different types of operators in Java, including arithmetic, relational, logical, and assignment operators, along with examples to understand their usage.

• Chapter 33: Trie in Java – Explore the implementation and use of Trie data structure in Java, a powerful tool for handling strings, with practical coding examples.

Other Series:

• Full Stack Java Development – Master the essentials of Java programming and web development with this series. Topics include object-oriented programming, design patterns, database interaction, and more.

• Full Stack JavaScript Development – Become proficient in JavaScript with this series covering everything from front-end to back-end development, including frameworks like React and Node.js.

---

Connect with Me
Stay updated with my latest posts and projects by following me on social media:

• LinkedIn: Connect with me for professional updates and insights.

• GitHub: Explore my repositories and contributions to various projects.

• LeetCode: Check out my coding practice and challenges.

Your feedback and engagement are invaluable. Feel free to reach out with questions, comments, or suggestions. Happy coding!

Rohit Gawande
Full Stack Java Developer | Blogger | Coding Enthusiast