coderz.py

In the previous topic, we got an introduction to Bit Manipulation in DSA. Let us now look at some examples using bit manipulation.

Given two integers x and y, return the Hamming distance between them:

Note: The Hamming distance between two integers is defined as the number of points where the corresponding bits differ.

i.e,

Input: x = 1, y = 4
Output: 2
Explanation:
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑
The above arrows point to position where the corresponding bits are different.

Solution:

class Solution {
    public int hammingDistance(int x, int y) {
   
    int xor = x ^ y; // perform bitwise XOR to get the difference
    int distance = 0;
    while (xor != 0) {
        if ((xor & 1) == 1) { // check if the rightmost bit is set
            distance++; // increment the distance counter
        }
        xor >>>= 1; // shift right by one bit
    }
    return distance;    
    }
}

• To obtain the difference between the two input integers, we first conduct a bitwise XOR operation on them.
• A while loop is then used to cycle through each bit of the XOR result, checking if the rightmost bit is set (i.e., equal to 1).
• If it is, we increment a Hamming distance counter.
• Finally, we use the unsigned right shift operator >>> to shift the XOR result one bit to the right in order to verify the next bit.

Given two binary strings a and b, return their sum as a binary string.

i.e,

Input: a = "11", b = "1"
Output: "100"

Solution:

   class Solution {
    public String addBinary(String a, String b) {
          int x = Integer.parseInt(a, 2);
    int y = Integer.parseInt(b, 2);
    int carry = 0;
    while (y != 0) {
        carry = x & y;
        x = x ^ y;
        y = carry << 1;
    }
    return Integer.toBinaryString(x);
    }
}

• use the Integer.parseInt() function with radix 2 to transform the binary input strings a and b to decimal integers.
• initialize a variable carry to 0 and use a while loop to perform bitwise addition until y becomes 0.
• Inside the while loop, calculate the carry by performing a bitwise AND operation on x and y, then update x by performing a bitwise XOR operation on x and y.
• update y by shifting the carry one bit to the left.

Given two integers dividend and divisor, divide two integers without using multiplication, division, and mod operator. Return the quotient after dividing dividend by divisor:

i.e,

Input: dividend = 10, divisor = 3
Output: 3
Explanation: 10/3 = 3.33333.. which is truncated to 3

Solution:

class Solution {
    public int divide(int A, int B) {
        if (A == 1 << 31 && B == -1) return (1 << 31) - 1;
        int a = Math.abs(A), b = Math.abs(B), res = 0, x = 0;
        while (a - b >= 0) {
            for (x = 0; a - (b << x << 1) >= 0; x++);
            res += 1 << x;
            a -= b << x;
        }
        return (A > 0) == (B > 0) ? res : -res;
    }
}

• handle the edge case where the dividend is the minimum integer value and the divisor is -1, which would cause an overflow.
• use a while loop to repeatedly subtract the divisor from the dividend until the dividend is less than the divisor.
• for loop is used to find the largest power of 2 such that the product of the divisor and the power of 2 is less than or equal to the remaining dividend.
• The value of this power of 2 is added to the result variable res, and the divisor is shifted left by this power of 2 (equivalent to multiplying by 2^x).
• The remaining dividend is then updated by subtracting this product.

Given an integer, return true if it is a power of two. Otherwise, return false:

i.e,

Input: n = 16
Output: true
Explanation: 24 = 16

Solution:

class Solution {
    public boolean isPowerOfTwo(int n) {
         if (n <= 0) {
        return false;
    }
    return (n & (n - 1)) == 0;
    }
}

• check if the input integer n is less than or equal to zero. If it is, the function returns false, since zero and negative numbers cannot be powers of two.
• the function uses the bitwise AND operator to check if n and n-1 have any bits in common.
• If n is a power of two, it will have only one bit set to 1, and n-1 will have all the bits to the right of this bit set to 1.
• Therefore, the bitwise AND operation will result in zero.
• If the result of the bitwise AND operation is zero, the function returns true, indicating that n is a power of two. Otherwise, the function returns false.

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

i.e,

Input: nums = [4,1,2,1,2]
Output: 4

Solution:

class Solution {
    public int singleNumber(int[] nums) {
         int result = 0;
        for (int num : nums) {
            result ^= num;
        }
        return result;
    }
}

• The XOR operator (^) returns a 1 in each bit position for which the corresponding bits of either but not both operands are 1.
• We can use this property to find the single non-repeating element in the array.
• Therefore, took the XOR of all elements in the array, and the result will be the single non-repeating element.

Note: also read about DSA: Bits Manipulation

Follow Me

Please follow me to read my latest post on programming and technology if you like my post.

https://www.instagram.com/coderz.py/

https://www.facebook.com/coderz.py