Bits

How to convert from decimal to any number system

vector<long long>getRepresentation(long long  n, int base){
	vector<long long>ret;	
	while(n){
		ret.push_back(n%base);
		n/=base;
	}	
	return ret;
}

Bitwise operations

Left-shifting n by k (n << k) multiplies n by 2^k. Right-shifting n by k (n >> k) divides n by 2^k (integer division, remainder dropped).

Helpful functions

to check weather the bit is 1 or 0

bool checkBit(ll n,ll i){
    return (n >> i)&1;
}

to check the number is odd or even

void checkParity(long long n){
	cout<<(n&1 ? "odd" : "even");
}

to toggle a certain bit

long long toggleBit(long long n, long long bit){
	return (n^(1ll<<bit));
}

to set a certain bit

long long setBit(long long n, long long bit){
	return (n|(1ll<<bit));
}

number of set bits

int countOnes(long long x){
	return __builtin_popcountll(x);
}

helpful information

$$2^n = 1 + \sum_{i<n} 2^i$$

One bit at position n > all bits below it combined

so if there any budget or getting highest number by changing bit so change the higher bit is more effective more that changing all the other bits

H. Maximal AND

this problem is apply this concept by giving an array of n numbers and k number of operations and we want to get the maximum number we can get by ANDING(&) all the the array members after flipping bits from 30th bit to the first bit so the information that will help us to get greedy is One bit at position n > all bits below it combined so we check if we could flip the 30th bit so the ANDING as big as possible if we could not do it we go to the 29th and so on until get the farest as possible

	long long ans = 0;
    for(int bit = 30; bit>=0; bit--){
        ll cost = 0;
        for(auto &x : a ){
            if (!checkBit(x, bit))cost++;
        } 
        if (cost<=k){
            k-=cost;
            ans+=1<<bit;
        }
    }

time complexity O(31 · n)

prefix sum for (XOR,AND and OR)

A XOR A = 0

that help us to cancel the extra part we add we we get the prefix sum of a range form [l,r] we will add the prefix to r XOR prefix[l-1]

prefix sum (XOR)

int n;cin>>n;
vector<long long>v(n+1);
vector<long long>prefXOR(n+1);
for(int i = 1; i <=n; i++)cin>>v[i];
for(int i = 1; i<= n; i++)prefXOR[i]=prefXOR[i-1]^v[i];
int q;cin>>q;
while(q--){
	int l,r;cin>>l>>r;
	cout<<prefXOR[r]^prefXOR[l-1]<<'\n';
}

time complexity building O(n) query O(1)

but we can’t do the same for OR and AND but we could count the number of 1 that appears for every bit and in the case of AND we just will ask the number of seted bits are equals to the range or not (all the bits in this range are 1s) in the case of OR we just ask about if there any 1 appears on that specific range of that bit

prefix sum (AND)

bool checkBit(long long n,long long bit){
    return (n >> bit)&1;
}

int n;cin>>n;
vector<long long>v(n+1);
for(int i = 1; i<=n; i++)cin>>v[i];
vector<vector<long long >>prefixBits(64,vector<long long>(n+1));
for(int bit = 0; bit < 64; bit++){
	for(long long i = 1; i<=n; i++){
		prefixBits[bit][i]=prefixBits[bit][i-1]+((v[i]>>bit)&1);
	}
}
long long q;cin>>q;
while(q--){
	long long l,r;cin>>l>>r; 
	long long ans = 0;	
	for(int bit = 0; bit < 64; bit++){
		int cnt=prefixBits[bit][r]-prefixBits[bit][l-1];
		if(cnt>=r-(l-1))ans+=(1ll<<bit);
	}
	cout<<ans<<'\n';
}

time complexity building O(n · 64) query O(64)

prefix sum (OR)

bool checkBit(long long n,long long bit){
    return (n >> bit)&1;
}

int n;cin>>n;
vector<long long>v(n+1);
for(int i = 1; i<=n; i++)cin>>v[i];
vector<vector<long long >>prefixBits(64,vector<long long>(n+1));
for(int bit = 0; bit < 64; bit++){
	for(long long i = 1; i<=n; i++){
		prefixBits[bit][i]=prefixBits[bit][i-1]+((v[i]>>bit)&1);
	}
}
long long q;cin>>q;
while(q--){
	long long l,r;cin>>l>>r; 
	long long ans = 0;	
	for(int bit = 0; bit < 64; bit++){
		int cnt=prefixBits[bit][r]-prefixBits[bit][l-1];
		if(cnt>0)ans+=(1ll<<bit);
	}
	cout<<ans<<'\n';
}

time complexity building O(n · 64) query O(64)

E. Iva & Pav

For a query (l, k), you fix l and slide r from l up to n. For each r, you compute f(l, r) = a[l] & a[l+1] & ... & a[r]. You want the largest r such that this AND value is still ≥ k.

we know how to get the prefix sum of ANDING operation on a specific range from above but we know have a real problem we could not try all the possible r the worst case will take a large time and will exceed the time limit because we have a lot of queries

so we want to minimize the time will be taken to search for r and we got lucky because AND result is monotonic so we could do a binary search to get the right r faster. so the code will be

typedef long long ll;
#define vi vector<ll>
#define el "\n"

bool checkBit(ll n,ll i){
    return (n >> i)&1;
}
void solve() {
    ll n;cin>>n;
    vi a(n+1);
    vector<vector<ll>> pref(32,vector<ll>(n+1));
    for(int i =1; i<=n; i++)cin>>a[i];
    for(int bit = 0; bit<32; bit++){
        for(int j = 1; j<=n; j++){
            pref[bit][j]= pref[bit][j-1]+checkBit(a[j], bit);
        }
    }
    ll q;cin>>q;
    while(q--){
        ll st,k;cin>>st>>k;
        ll l = st, r= n;
        ll ans =-1;
        while (r>=l){
            ll mid = l+(r-l)/2;
            ll andValue=0;
            for(int bit = 0; bit<32; bit++){
                ll count1=pref[bit][mid]-pref[bit][st-1];
                if(count1==mid-st+1)andValue+=1ll<<bit;
            }
            if (andValue>=k)ans=mid,l =mid+1;
            else r=mid-1;
        }
        cout<<ans<<" ";
    }
    cout<<el;
}

time complexity building the pref O(32 . n) , query O(32 . log n) the 32 for the building and query is contain so we could remove it and we have q number of queries so the total time compelxity is O(n+(q.log n))

AND monotonic decreasing , OR monotonic increasing XOR and XOR is not monotonic

Bit mask

**bit mask is just a number make no scence if we look at it as a decimal representation but if we looked at it’s binary representation we could see that it means takes that leaves that so it be really helpful at the subset problemes **

B. Preparing Olympiad

given n problems (n ≤ 15) each with a difficulty, we want to count how many subsets of at least 2 problems have total difficulty between l and r, and the difference between hardest and easiest problem in the subset is at least x.

since n ≤ 15, there are only 2^15 = 32768 possible subsets, so we can just try all of them with a bitmask and check the conditions directly on each one.

for each mask go through every bit i and check if it’s set if so include that element in the sum and update the running min/max for that subset. after checking all bits test if sum is in [l,r] and max-min >= x if so count it.

void solve() {
    ll n,l,r,x;cin>>n>>l>>r>>x;
    vi c(n);
    for(auto &val : c) cin>>val;
    ll ans = 0;
    for(int mask = 0; mask < 1<<n; mask++){
        ll sum = 0, mn = oo, mx = -oo;
        for(int i = 0; i < n; i++){
            if(mask >> i & 1){
                sum += c[i];
                mn = min(mn, c[i]);
                mx = max(mx, c[i]);
            }
        }
        if(sum >= l && sum <= r && (mx - mn) >= x){
            ans++;
        }
    }
    cout << ans << el;
}

time complexity is O($2^n$ . n), and n up to 15 .

helpful builtin functions

__builtin_clz(x)

This function is used to count the leading zeros of the integer. Note : clz = count leading zero’s. 
Example: It counts number of zeros before the first occurrence of one(set bit). 

a = 16 Binary form of 16 is 00000000 00000000 00000000 00010000
Output: 27

#include <bits/stdc++.h>

using namespace std;

​

int main()

{

    int n = 16;

    cout<<"Count of leading zeros before 1 in "<< n <<" is "<<__builtin_clz(n);

    return 0;

}

Output

Count of leading zeros before 1 in 16 is 27

Note: __builtin_clz(x) This function only accept unsigned values 
Note: Similarly you can use __builtin_clzl(x) & __builtin_clzll(x) for long and long long data types.

__builtin_ctz(x)

This function is used to count the trailing zeros of the given integer. Note : ctz = count trailing zeros. 
Example: Count no of zeros from last to first occurrence of one(set bit). 

a = 16
Binary form of 16 is 00000000 00000000 00000000 00010000
Output: ctz = 4

#include <bits/stdc++.h>

using namespace std;

​
int main()

{

    int n = 16;

    cout<<"Count of zeros from last to first occurrence of one is  "<< __builtin_ctz(n);

    return 0;

}

Output

Count of zeros from last to first occurrence of one is 4

Note: Similarly you can use __builtin_ctzl(x) & __builtin_ctzll(x) for long and long long data types.

Bitset 

is a container that represents a fixed-size sequence of bits. A bitset allows you to manipulate individual bits efficiently, making it useful in problems related to bitwise operations, such as checking flags, implementing binary representations.

Bitset is defined as the std::bitset class template inside the < bitset > header file.

helpful functions for < bitset >