bitwise cp‐questions

Table of Contents

1. Bit Manipulation
   • Number of Bits to Flip to Convert A to B
2. Arithmetic Operations
   • Integer Division without Using Division Operator
3. Finding Unique Elements in Arrays
   • Single Element in Array Where Every Element Appears Thrice
   • Two Unique Elements in an Array
4. Generating Subsets
   • Generating All Subsets of a Set

---

Bit Manipulation

Number of Bits to Flip to Convert A to B

Question: How many bits need to be flipped to convert integer a to integer b?

Code Explanation:

#include<bits/stdc++.h>
using namespace std;

int main(){
    int a, b;
    cin >> a >> b;
    int ans = a ^ b, count = 0;
    while (ans) {
        ans &= ans - 1;
        count++;
    }
    cout << count;
}

Explanation:

• a ^ b computes the XOR of a and b, resulting in a number where each bit represents a difference between the corresponding bits of a and b.
• The loop while (ans) { ans &= ans - 1; count++; } uses a technique known as Brian Kernighan’s Algorithm to count the number of set bits (1s) in the XOR result, which corresponds to the number of bits that differ between a and b.

---

Arithmetic Operations

Integer Division without Using Division Operator

Question: Perform integer division of two integers div and dvo without using the division operator.

Code Explanation:

#include<bits/stdc++.h>
using namespace std;

int main() {
    int div, dvo;
    cin >> div >> dvo;
    int sign = div >= 0 && dvo >= 0 || div < 0 && dvo < 0 ? 1 : -1;
    long n = abs(div);
    long d = abs(dvo);
    int count;
    long ans = 0;
    while (n >= d) {
        count = 0;
        while (n >= (d << count + 1)) count++;
        ans += 1 << count;
        n -= d << count;
    }
    if (ans >= pow(2, 31)) ans = 2147483648;
    cout << sign * ans;
}

Explanation:

• This code performs integer division using bitwise operations.
• It determines the sign of the result based on the input values.
• The main loop subtracts the largest possible multiple of dvo from div using bitwise left shifts and accumulates the result in ans.
• It ensures the result is within the 32-bit signed integer range.

---

Finding Unique Elements in Arrays

Single Element in Array Where Every Element Appears Thrice

Question: Find the element that appears exactly once in an array where every other element appears thrice.

Code Explanation:

#include<bits/stdc++.h>
using namespace std;

int usingOneAndTwo(vector<int> v) {
    int one = 0, two = 0;
    for (int i : v) {
        one = one ^ i & ~two;
        two = two ^ i & ~one;
    }
    return one;
}

int main() {
    cout << usingOneAndTwo({1, 1, 1, 2, 2, 2, 3});
}

Explanation:

• This algorithm uses two variables, one and two, to keep track of bits that have appeared once and twice, respectively.
• For each element in the array, it updates these variables such that only the unique element remains in one at the end.

Two Unique Elements in an Array

Question: Find the two unique elements in an array where every other element appears twice.

Code Explanation:

#include<bits/stdc++.h>
using namespace std;

pair<int, int> single2(vector<int> arr) {
    int ans = 0, b1 = 0, b2 = 0;
    for (int i : arr) ans ^= i;
    int pos = ans & (ans - 1) ^ ans;
    for (int i : arr) { 
        if (i & pos) b1 ^= i; 
        else b2 ^= i;
    }
    return {b1, b2};
}

int main() {
    pair<int, int> p = single2({2, 2, 3, 3, 4, 5});
    cout << p.first << " " << p.second << endl;
}

Explanation:

• The XOR of all elements gives ans, which is the XOR of the two unique numbers.
• The bit position where the two numbers differ is found using int pos = ans & (ans - 1) ^ ans;.
• The array is then partitioned based on this bit, and XOR within each partition yields the two unique numbers.

---

Generating Subsets

Generating All Subsets of a Set

Question: Generate all possible subsets of a set containing numbers from 1 to num.

Code Explanation:

#include<bits/stdc++.h>
using namespace std;

int main() {
    int num;
    cin >> num;
    vector<vector<int>> ans;
    vector<int> temp;
    for (int i = 0; i < (1 << num); i++) {
        temp.clear();
        for (int j = 0; j < num; j++) {
            if ((i & (1 << j)) != 0) temp.push_back(j + 1);
        }
        ans.push_back(temp);
    }
    for (vector<int> i : ans) {
        for (int j : i) cout << j << ",";
        cout << endl;
    }
    return 0;
}

Explanation:

• This code generates all subsets of a set containing numbers from 1 to num using bitwise operations.
• The outer loop iterates over all possible combinations (2^num).
• The inner loop checks which elements are present in the subset using bitwise AND.
• The subsets are collected in ans and then printed.

---

Each section provides a clear explanation of the problem, the purpose of the code, and a detailed breakdown of how the code works. This structure makes it easy for users to understand and learn from the provided examples.