Bitwise Operations and Bitmasks

Bitwise operators manipulate the binary representation of integers. They provide compact flags and subset representations, which later support visited-resource states and bitmask DP. Use unsigned operands and controlled shift counts to avoid signed-representation pitfalls. This lesson demonstrates individual bit updates, an explicitly limited complement, shifts and full subset enumeration for a small number of values.

Prerequisites: Data types; binary representation; loops; subset generation.

Build the idea

1. 1. Distinguish bits from Boolean logic

   Bitwise &, | and ^ operate independently at each bit position: AND keeps bits set in both, OR keeps bits set in either, XOR keeps bits set in exactly one. ~ flips every bit of the unsigned representation. These differ from logical &&, || and !, which interpret entire values as true/false and may short-circuit. Bit positions start at zero from the least significant side.

2. 2. Build and use a safe mask

   1ULL<<k creates a mask with bit k set. Test using (x&bit)!=0, set using x|bit, clear using x&~bit and toggle using x^bit. The ULL suffix ensures a wide unsigned left operand. A shift count must be nonnegative and strictly below the operand width; a wider destination cannot rescue an already invalid narrow shift such as 1<<40.

3. 3. Define the complement width

   Unsigned long long has at least 64 value bits, so ~10 flips many more than four displayed bits. To complement only the lowest eight positions, use (~x)&255ULL. For x=10 (binary 1010) that result is 245. Shifting left one doubles the unsigned numeric value when no high bits are discarded; right shift divides a nonnegative unsigned value by two. This contract limits x to 32 bits so x<<1 still fits.

4. 4. Map subsets to masks

   For n objects, bit i indicates whether object i is included. Masks 0 through (1ULL<<n)−1 enumerate every subset once, including empty mask zero. For [3,5], masks 00,01,10,11 give sums 0,3,5,8; their total is 16. The program sums all subset sums to make enumeration visible through a compact output, rather than printing exponentially many lines.

5. 5. Estimate before allocating or enumerating

   There are 2ⁿ masks, and the direct inner scan checks n bits per mask. n≤20 keeps this demonstration manageable. Making a mask type wider does not make 2^60 subsets feasible. Use std::numeric_limits<Unsigned>::digits when writing a generic width-aware interface, and distinguish unsigned modulo arithmetic from undefined signed overflow.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
int main(){
    unsigned long long x;
    int k,n;
    std::cin>>x>>k>>n;
    unsigned long long bit=1ULL<<k; // Contract: 0<=k<=31, safely below width.
    std::cout<<((x&bit)!=0)<<' '<<(x|bit)<<' '<<(x&~bit)<<' '<<(x^bit)<<'\n';
    std::cout<<((~x)&255ULL)<<' '<<(x<<1)<<' '<<(x>>1)<<'\n';
    std::vector<long long>values(n);
    for(auto&v:values){
        std::cin>>v;
    }
    unsigned long long masks=1ULL<<n;
    long long total=0;
    for(unsigned long long mask=0;mask<masks;++mask){
        long long sum=0;
        for(int i=0;i<n;++i){
            if(mask&(1ULL<<i)){
                sum+=values[i];
            }
        }
        total+=sum;
    }
    std::cout<<masks<<' '<<total<<'\n';
}

Complexity analysis

O(n·2ⁿ+1) time for direct subset-sum enumeration and O(n) input storage with O(1) auxiliary mask/sum state. Individual bounded-word bit operations are O(1). x≤2^32−1, 0≤k≤31, n≤20 and |value|≤10^9 make every shift and the total of all subset sums safe in unsigned/long long as used.

Example input and output

Read x k n, 0≤x≤4294967295, 0≤k≤31, 0≤n≤20, then n signed values |value|≤10^9. Print bit-test/set/clear/toggle; low-eight-bit complement/left-shift/right-shift; then subset count and total of all subset sums.

Input

10 1 2
3 5

Output

1 10 8 8
245 20 5
4 16

Bit 1 is set in 10. Clearing or toggling it gives 8; the four subset sums are 0,3,5,8.

Practical applications

Use for compact feature sets, subset enumeration, parity tricks and state encodings. Use an explicit vector<bool> or other representation when the set is larger or clearer that way. Bitmask DP adds reusable subset states; bit operations alone do not reduce exponential enumeration to polynomial time.

Check your understanding

Why write 1ULL before a wide shift?

Put it into practice

Count only subsets of exactly k selected values without nonstandard compiler builtins.