basic-level-bit.cpp

// ⚡ 🟢 EASY BIT MANIPULATION (Foundation Level)

// 👉 Focus: Understand operators + basic tricks

// 🔹 Core Operators (MUST KNOW)
// AND & → check bit
// OR | → set bit
// XOR ^ → toggle / difference ⭐
// NOT ~
// Left shift << (multiply by 2)
// Right shift >> (divide by 2)
// 🔹 Basic Bit Tricks
// Check if number is even/odd (n & 1) ⭐
// Check if ith bit is set
// Set ith bit
// Clear ith bit
// Toggle ith bit





// 🔹 Classic Problems
// Check power of 2 (n & (n-1)) == 0 ⭐⭐⭐
// Count set bits (naive)
// Remove last set bit (n & (n-1)) ⭐
// Find single number (using XOR) ⭐⭐⭐ i want to all above 15 topic to explain me in detailed with mathmatical working approaches,and also used case ,and also each topic used code in c++ complete code 

// Great — this is exactly how you should build bit manipulation foundations. I’ll explain all 15 topics deeply, including:

// 💡 Mathematical intuition
// ⚙️ Working logic
// 📌 Use cases
// 💻 Clean C++ code






// ⚡ 🟢 1. AND Operator (&)
// 💡 Concept
// Bitwise AND compares each bit:

// 1 & 1 = 1  
// otherwise = 0
// Example:
// 5 = 101  
// 3 = 011  
// -----------
//     001 = 1
// 📐 Mathematical Insight

// Acts like bit filtering → keeps only common 1s.

// 📌 Use Cases
// Check if a bit is ON
// Masking bits
// 💻 Code
// #include<bits/stdc++.h>
// using namespace std;

// int main(){
//     int a = 5, b = 3;
//     cout << (a & b); // Output: 1
// }



// ⚡ 🟢 2. OR Operator (|)
// 💡 Concept
// 1 | 0 = 1  
// 1 | 1 = 1  
// 0 | 0 = 0
// Example:
// 5 = 101  
// 3 = 011  
// -----------
//     111 = 7
// 📐 Insight

// Acts like bit merging

// 📌 Use Cases
// Set bits
// 💻 Code
// cout << (5 | 3); // 7




// ⚡ 🟢 3. XOR Operator (^) ⭐
// 💡 Concept
// 1 ^ 1 = 0  
// 1 ^ 0 = 1  
// Example:
// 5 = 101  
// 3 = 011  
// -----------
//     110 = 6
// 📐 Mathematical Properties
// a ^ a = 0
// a ^ 0 = a
// Commutative & Associative
// 📌 Use Cases
// Find unique element
// Toggle bits
// 💻 Code
// cout << (5 ^ 3); // 6




// ⚡ 🟢 4. NOT Operator (~)
// 💡 Concept
// Flips all bits
// ~5 = -(5+1) = -6
// 📐 Insight
// Uses 2’s complement
// 📌 Use Cases
// Bit inversion
// 💻 Code
// cout << (~5); // -6



// ⚡ 🟢 5. Left Shift (<<)
// 💡 Concept
// n << k = n × 2^k
// Example:
// 5 << 1 = 10
// 📌 Use Cases
// Fast multiplication
// 💻 Code
// cout << (5 << 1); // 10



// ⚡ 🟢 6. Right Shift (>>)
// 💡 Concept
// n >> k = n / 2^k
// 📌 Use Cases
// Fast division
// 💻 Code
// cout << (8 >> 1); // 4



// ⚡ 🟢 7. Check Even/Odd (n & 1) ⭐
// 💡 Concept
// Last bit determines parity:
// 0 → even
// 1 → odd
// 📐 Why?
// Binary:
// Even → last bit = 0  
// Odd → last bit = 1
// 📌 Use Cases
// Fast parity check
// 💻 Code
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n = 7;
    if(n & 1) cout << "Odd";
    else cout << "Even";
}




// ⚡ 🟢 8. Check i-th Bit
// 💡 Concept
// (n >> i) & 1
// 📐 Logic
// Shift ith bit to last position
// 💻 Code
bool isSet(int n, int i){
    return (n >> i) & 1;
}




// ⚡ 🟢 9. Set i-th Bit
// 💡 Concept
// n | (1 << i)
// 📌 Use Case
// Turn ON a bit
// 💻 Code
int setBit(int n, int i){
    return n | (1 << i);
}




// ⚡ 🟢 10. Clear i-th Bit
// 💡 Concept
// n & ~(1 << i)
// 📐 Logic
// Create mask with 0 at ith position
// 💻 Code
int clearBit(int n, int i){
    return n & ~(1 << i);
}




// ⚡ 🟢 11. Toggle i-th Bit
// 💡 Concept
// n ^ (1 << i)
// 📌 Use Case
// Flip bit
// 💻 Code
int toggleBit(int n, int i){
    return n ^ (1 << i);
}



// ⚡ 🟢 12. Power of 2 Check ⭐⭐⭐
// 💡 Concept
// n & (n-1) == 0
// 📐 Why it works?
// Power of 2 has only one set bit
// Example:
// 8 = 1000  
// 7 = 0111  
// AND = 0000
// 💻 Code
bool isPowerOfTwo(int n){
    return n > 0 && (n & (n - 1)) == 0;
}




// ⚡ 🟢 13. Count Set Bits (Naive)
// 💡 Concept
// Check each bit
// 💻 Code
int countBits(int n){
    int count = 0;
    while(n){
        count += (n & 1);
        n >>= 1;
    }
    return count;
}



// ⚡ 🟢 14. Remove Last Set Bit ⭐
// 💡 Concept
// n & (n-1)
// 📐 Why?
// Removes lowest 1 bit
// Example:
// 12 = 1100  
// 11 = 1011  
// AND = 1000
// 💻 Code
int removeLastSetBit(int n){
    return n & (n - 1);
}




// ⚡ 🟢 15. Find Single Number (XOR) ⭐⭐⭐
// 💡 Problem
// All numbers appear twice except one
// 💡 Idea
// a ^ a = 0  
// 0 ^ x = x
// 📐 Logic
// All duplicates cancel out


// 💻 Code
#include<bits/stdc++.h>
using namespace std;
int singleNumber(vector<int>& nums){
    int res = 0;
    for(int x : nums){
        res ^= x;
    }
    return res;
}
int main(){
    vector<int> nums = {2,2,1};
    cout << singleNumber(nums); // 1
}








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

/* ================= BASIC OPERATIONS ================= */

// Check even/odd using AND
bool isOdd(int n){
    return n & 1;
}

// Check ith bit
bool isBitSet(int n, int i){
    
    return (n >> i) & 1;

}

// Set ith bit
int setBit(int n, int i){
    return n | (1 << i);
}

// Clear ith bit
int clearBit(int n, int i){
    return n & ~(1 << i);
}

// Toggle ith bit
int toggleBit(int n, int i){
    return n ^ (1 << i);
}

// Remove last set bit
int removeLastSetBit(int n){
    return n & (n - 1);
}

// Count set bits (naive)
int countSetBits(int n){
    int cnt = 0;
    while(n){
        cnt += (n & 1);
        n >>= 1;
    }
    return cnt;
}

// Power of 2 check
bool isPowerOfTwo(int n){
    return n > 0 && (n & (n - 1)) == 0;
}

// Find single number using XOR
int findSingle(vector<int>& arr){
    int res = 0;
    for(int x : arr){
        res ^= x;
    }
    return res;
}

/* ================= MAIN DEMO ================= */

int main(){
    
    int n = 10; // 1010
    int i = 1;

    cout << "Number: " << n << endl;

    // 1. AND Operator (check bit)
    cout << "Is bit " << i << " set? " << (n & (1 << i)) << endl;

    // 2. OR Operator (set bit)
    cout << "Set bit " << i << ": " << (n | (1 << i)) << endl;

    // 3. XOR Operator (toggle bit)
    cout << "Toggle bit " << i << ": " << (n ^ (1 << i)) << endl;

    // 4. NOT Operator
    cout << "NOT of n: " << ~n << endl;

    // 5. Left Shift
    cout << "n << 1 (multiply by 2): " << (n << 1) << endl;

    // 6. Right Shift
    cout << "n >> 1 (divide by 2): " << (n >> 1) << endl;

    // 7. Even/Odd
    cout << "Even or Odd: " << (isOdd(n) ? "Odd" : "Even") << endl;

    // 8. Check ith bit
    cout << "Check ith bit: " << isBitSet(n, i) << endl;

    // 9. Set ith bit
    cout << "After setting ith bit: " << setBit(n, i) << endl;

    // 10. Clear ith bit
    cout << "After clearing ith bit: " << clearBit(n, i) << endl;

    // 11. Toggle ith bit
    cout << "After toggling ith bit: " << toggleBit(n, i) << endl;

    // 12. Power of 2
    cout << "Is power of 2? " << (isPowerOfTwo(n) ? "Yes" : "No") << endl;

    // 13. Count set bits
    cout << "Number of set bits: " << countSetBits(n) << endl;

    // 14. Remove last set bit
    cout << "After removing last set bit: " << removeLastSetBit(n) << endl;

    // 15. XOR Single Number
    vector<int> arr = {2, 3, 2, 4, 4};
    cout << "Single number (XOR): " << findSingle(arr) << endl;

    return 0;
}