Data Structures and Algorithms(DSA) Concept — Bit Manipulation- Part 1

Topics : What is Bit ? , Binary number system , Bitwise Operations , DSA interview questions on Bit manipulation.

What is a Bit?

A bit, short for “binary digit,” is the most basic unit of information in computing and digital communications. It can hold one of two values, typically represented as:

• 0 (off, false, no)
• 1 (on, true, yes)

Bits are the building blocks for all digital data, and by combining them, we can represent more complex information.

How is a Bit Calculated?

A bit itself is a fundamental concept and doesn’t require calculation in isolation. However, bits come into play when dealing with larger data structures like bytes, which consist of 8 bits. The value of a byte is determined by the combination of its bits. For example, the binary number 10101010 represents a specific byte.

When we perform bit manipulation, we use operations that directly manipulate bits within a binary number. These operations include bitwise AND, OR, XOR, NOT, shifts, and rotations. Each operation treats the number as a sequence of bits and applies the logic accordingly.

Binary Number Systems

The binary number system is the foundation of all binary code used in computers and digital systems. In binary, each digit (or bit) is a power of 2, starting from the rightmost bit. Here’s how binary works:

• Binary Digits (Bits): The binary system uses only two digits: 0 and 1.
• Positional Value: Each position in a binary number represents a power of 2, starting with 202⁰²⁰ at the rightmost bit.

For example, the binary number 1101 can be understood as:

• 1 x 2³ (8)
• 1 x 2² (4)
• 0 x 2¹ (0)
• 1 x 2⁰ (1)

Summing these values gives us 8+4+0+1=13. Therefore, the binary number 1101 represents the decimal number 13.

Basic Bitwise Operations

1. Bitwise AND (&): Compares each bit of two numbers and returns a new number whose bits are set to 1 only if both corresponding bits of the original numbers are 1.

• Example: 1100 & 1010 = 1000

2. Bitwise OR (|): Compares each bit of two numbers and returns a new number whose bits are set to 1 if either of the corresponding bits of the original numbers are 1.

• Example: 1100 ∣ 1010 =1110

3. Bitwise XOR (^): Compares each bit of two numbers and returns a new number whose bits are set to 1 if the corresponding bits of the original numbers are different.

• Example: 1100 ^ 1010 = 0110

4. Bitwise NOT (~): Inverts all the bits of a number.

• Example: 1100=0011 (assuming a 4-bit number for simplicity)

5. Bitwise Shift Left (<<): Shifts all the bits of a number to the left by a specified number of positions, inserting zeros from the right.

• Example: 1100<<1=1000

6. Bitwise Shift Right (>>): Shifts all the bits of a number to the right by a specified number of positions, discarding bits shifted off.

• Example: 1100>>1=0110

Applications of Bit Manipulation

Bit manipulation is used in various computing tasks such as:

• Setting, clearing, or toggling specific bits: Useful for controlling individual flags or options.
• Performing fast mathematical operations: Certain calculations can be optimized using bitwise operations.
• Data compression and encryption: Bits can be manipulated to encode data efficiently or to apply cryptographic transformations.
• Graphics and gaming: Often used to handle color values, image processing, and efficient computations in rendering algorithms.

Understanding and utilizing bit manipulation is crucial for low-level programming, optimizing performance, and working with hardware or system-level applications. As you dive deeper into this topic, you’ll find that mastering these operations can greatly enhance your ability to write efficient and powerful code.

Lets look at a couple of DSA interview problems based on bit Manipulation .

Q 1. Given an array of N elements where all elements appear twice except for one element which appears exactly once .

Find the single number.

Eg : 

A = [ 6, 9, 6, 10, 9 ]

Lets see if we can use any of the bit wise operators we just learned to 
solve this problem 
let take the integer 6 which can be written in bits as 

6 = 1 1 0

then using XOR '^' bit wise operator,
 
6 ^ 6 = 1 1 0 ^ 1 1 0 
      
      = 0 0 0
      
      = 0

so we can remove common elements using '^' operator.

lets see this in code.

public void singleElement(int[]  A){

 int ans=0;

  for ( int i=0 ; i<A.length ; i++ ){
      
      ans = ans ^ A[i];

  }

  System.out.print(ans);

}

In part 2 we will explore more DSA interview problems related to Bit manipulation.

Data Structures and Algorithms(DSA) Concept — Bit Manipulation- Part 2