BitManipulation

Bitwise Basics in C++

Bitwise operations are fundamental to many low-level programming tasks, and C++ provides a comprehensive set of operators to manipulate individual bits in an integer. Here, we'll explore the primary bitwise operators and demonstrate their usage through various code examples. Each code snippet will include a brief explanation to aid understanding.

Certainly! Here's how you can structure the content for a GitHub wiki, complete with a table of contents:

---

Bitwise Basics in C++

Bitwise operations are fundamental to many low-level programming tasks, and C++ provides a comprehensive set of operators to manipulate individual bits in an integer. Here, we'll explore the primary bitwise operators and demonstrate their usage through various code examples. Each code snippet will include a brief explanation to aid understanding.

Table of Contents

1. Bitwise Operators
2. Examples and Explanations
   • Basic Bitwise Operations
   • Binary to Decimal Conversion
   • Check if the ith Bit is Set
   • Check if a Number is a Power of 2
   • Clear the ith Bit of a Number
   • Count Number of Set Bits
   • Decimal to Binary Conversion
   • Check if a Number is Odd or Even
   • Remove the Last Set Bit
   • Set the ith Bit of a Number
   • Swap Two Numbers Using Bitwise Operations
   • XOR of All Numbers from 1 to n
   • Removing the Last Set Bit Using Different Techniques
3. cp-question

Bitwise Operators

1. AND (&)
2. OR (|)
3. XOR (^)
4. Left Shift (<<)
5. Right Shift (>>)
6. NOT (~)

Examples and Explanations

Basic Bitwise Operations

#include<iostream>
using namespace std;

int main() {
    int a = 0, b = -6;

    cout << (a & b) << endl;  // AND operation
    cout << (a | b) << endl;  // OR operation
    cout << (a ^ b) << endl;  // XOR operation
    cout << (b >> 1) << endl; // Right shift
    cout << (b << 1) << endl; // Left shift
    cout << ~b << endl;       // NOT operation

    return 0;
}

Explanation:

• a & b performs a bitwise AND.
• a | b performs a bitwise OR.
• a ^ b performs a bitwise XOR.
• b >> 1 shifts b right by 1 bit.
• b << 1 shifts b left by 1 bit.
• ~b inverts all the bits of b.

Binary to Decimal Conversion

#include<iostream>
#include<string>
#include<cmath>
using namespace std;

int main() {
    int ans = 0, p = 0;
    string bin = "100";

    while (!bin.empty()) {
        ans += (bin.back() - '0') * pow(2, p);
        p++;
        bin.pop_back();
    }

    cout << ans;
    return 0;
}

Explanation:

• Converts a binary string "100" to its decimal equivalent.

Check if the ith Bit is Set

#include<iostream>
using namespace std;

int main() {
    int num, i;
    cin >> num >> i;
    cout << (num & (1 << i));
    return 0;
}

Explanation:

• Checks if the ith bit of num is set (1) or not (0).

Check if a Number is a Power of 2

#include<iostream>
using namespace std;

int main() {
    int num;
    cin >> num;

    if ((num & (num - 1)) == 0) {
        cout << "Power of 2: " << num;
    } else {
        cout << "Not a power of 2: " << num;
    }

    return 0;
}

Explanation:

• Uses the property that powers of 2 have exactly one bit set.

Clear the ith Bit of a Number

#include<iostream>
using namespace std;

int main() {
    int num, i;
    cin >> num >> i;
    cout << (num & ~(1 << i));
    return 0;
}

Explanation:

• Clears (sets to 0) the ith bit of num.

Count Number of Set Bits

#include<iostream>
using namespace std;

int main() {
    int num;
    cin >> num;
    int count = 0;

    while (num) {
        num &= num - 1;
        count++;
    }

    cout << count;
    return 0;
}

Explanation:

• Counts the number of 1s in the binary representation of num.

Decimal to Binary Conversion

#include<iostream>
#include<string>
using namespace std;

int main() {
    string s = "";
    int n;
    cin >> n;

    while (n) {
        s = to_string(n % 2) + s;
        n /= 2;
    }

    cout << s;
    return 0;
}

Explanation:

• Converts a decimal number to its binary representation.

Check if a Number is Odd or Even

#include<iostream>
using namespace std;

int main() {
    int num;
    cin >> num;
    cout << (num & 1);
    return 0;
}

Explanation:

• Uses the last bit to determine if num is odd (1) or even (0).

Remove the Last Set Bit

#include<iostream>
using namespace std;

void forloop(int num) {
    int mask, ans;
    for (int i = 0; i < 32; i++) {
        mask = 1 << i;
        ans = num >> i;
        if (ans & 1 != 0) {
            cout << (num & ~mask);
            return;
        }
    }
}

void whileloop(int num) {
    int temp = num, count = 0;
    while (temp) {
        if (temp & 1 != 0) break;
        count++;
        temp >>= 1;
    }
    temp = 1 << count;
    cout << (num & ~temp);
}

void bitwisemanipulation(int num) {
    cout << (num & (num - 1));
}

int main() {
    int num = 5;
    // forloop(num);
    // whileloop(num);
    bitwisemanipulation(num);
    return 0;
}

Explanation:

• Shows different methods to remove the last set bit from num.

Set the ith Bit of a Number

#include<iostream>
using namespace std;

int main() {
    int n, i;
    cin >> n >> i;
    n |= 1 << i;
    cout << n;
    return 0;
}

Explanation:

• Sets the ith bit of n to 1.

Swap Two Numbers Using Bitwise Operations

#include<iostream>
using namespace std;

int main() {
    int a = 5, b = 6;
    cout << a << " " << b << endl;
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;
    cout << a << " " << b << endl;
    return 0;
}

Explanation:

• Swaps the values of a and b without using a temporary variable.

XOR of All Numbers from 1 to n

#include<iostream>
using namespace std;

int xorn(int num) {
    int temp = num % 4;
    if (temp == 0) return num;
    else if (temp == 1) return 1;
    else if (temp == 2) return num + 1;
    else return 0;
}

int main() {
    int num;
    cin >> num;
    cout << xorn(num);
    return 0;
}

Explanation:

• Computes the XOR of all numbers from 1 to num.

Removing the Last Set Bit Using Different Techniques

#include<iostream>
using namespace std;

void forloop(int num) {
    int mask, ans;
    for (int i = 0; i < 32; i++) {
        mask = 1 << i;
        ans = num >> i;
        if (ans & 1 != 0) {
            cout << (num & ~mask);
            return;
        }
    }
}

void whileloop(int num) {
    int temp = num, count = 0;
    while (temp) {
        if (temp & 1 != 0) break;
        count++;
        temp >>= 1;
    }
    temp = 1 << count;
    cout << (num & ~temp);
}

void bitwisemanipulation(int num) {
    cout << (num & (num - 1));
}

int main() {
    int num = 5;
    // forloop(num);
    // whileloop(num);
    bitwisemanipulation(num);
    return 0;
}

Explanation:

• Demonstrates three different ways to remove the last set bit of num.

These examples cover a broad spectrum of bitwise operations, illustrating how to manipulate and query individual bits efficiently in C++.