When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

Errichto's blog

By Errichto, 4 years ago, In English

You can watch my Youtube video (link) with the same content as this blog. Anyway, enjoy.

Introduction

Let's learn bitwise operations that are useful in Competitive Programming. Prerequisite is knowing the binary system. For example, the following must be clear for you already.

$$$13 = 1 \cdot 8 + 1 \cdot 4 + 0 \cdot 2 + 1 \cdot 1 = 1101_{(2)} = 00001101_{(2)}$$$

Keep in mind that we can pad a number with leading zeros to get the length equal to the size of our type size. For example, char has $$$8$$$ bits and int has $$$32$$$.

Bitwise AND, OR, XOR

You likely already know basic logical operations like AND and OR. Using if(condition1 && condition2) checks if both conditions are true, while OR (c1 || c2) requires at least one condition to be true.

Same can be done bit-per-bit with whole numbers, and it's called bitwise operations. You must know bitwise AND, OR and XOR, typed respectively as & | ^, each with just a single character. XOR of two bits is $$$1$$$ when exactly one of those two bits is $$$1$$$ (so, XOR corresponds to != operator on bits). There's also NOT but you won't use it often. Everything is explained in Wikipedia but here's an example for bitwise AND. It shows that 53 & 28 is equal to $$$20$$$.

53 = 110101
28 = 11100

  110101
&  11100  // imagine padding a shorter number with leading zeros to get the same length
 -------
  010100  =  20
C++ code for experimenting

Shifts

There are also bitwise shifts << and >>, not having anything to do with operators used with cin and cout.

As the arrows suggest, the left shift << shifts bits to the left, increasing the value of the number. Here's what happens with 13 << 2 — a number $$$13$$$ shifted by $$$2$$$ to the left.

    LEFT SHIFT                             RIGHT SHIFT
       13 =     1101                          13 =   1101
(13 << 2) =   110100                   (13 >> 2) =     11   

If there is no overflow, an expression x << b is equal to $$$x \cdot 2^b$$$, like here we had (13 << 2) = 52.

Similarly, the right shift >> shifts bits to the right and some bits might disappear this way, like bits 01 in the example above. An expression x >> b is equal to the floor of $$$\frac{x}{2^b}$$$. It's more complicated for negative numbers but we won't discuss it.

So what can we do?

$$$2^k$$$ is just 1 << k or 1LL << k if you need long longs. Such a number has binary representation like 10000 and its AND with any number $$$x$$$ can have at most one bit on (one bit equal to $$$1$$$). This way we can check if some bit is on in number $$$x$$$. The following code finds ones in the binary representation of $$$x$$$, assuming that $$$x \in [0, 10^9]$$$:

for(int i = 0; i < 30; i++) if((x & (1 << i)) != 0) cout << i << " ";

(we don't have to check $$$i = 30$$$ because $$$2^{30} > x$$$)

And let's do that slightly better, stopping for too big bits, and using the fact that if(value) checks if value is non-zero in C++.

for(int i = 0; (1 << i) <= x; i++) if(x & (1 << i)) cout << i << " ";

Consider this problem: You are given $$$N \leq 20$$$ numbers, each up to $$$10^9$$$. Is there a subset with sum equal to given goal $$$S$$$?

It can be solved with recursion but there's a very elegant iterative approach that iterates over every number $$$x$$$ from $$$0$$$ to $$$2^n - 1$$$ and considers $$$x$$$ to be a binary number of length $$$n$$$, where bit $$$1$$$ means taking a number and bit $$$0$$$ is not taking. Understanding this is crucial to solve any harder problems with bitwise operations. Analyze the following code and then try to write it yourself from scratch without looking at mine.

solution code

Two easy problems where you can practice iterating over all $$$2^N$$$ possibilities:
- https://codeforces.com/problemset/problem/1097/B
- https://codeforces.com/problemset/problem/550/B

Speed

Time complexity of every bitwise operation is $$$O(1)$$$. These operations are very very fast (well, popcount is just fast) and doing $$$10^9$$$ of them might fit in 1 second. You will later learn about bitsets which often produce complexity like $$$O(\frac{n^2}{32})$$$, good enough to pass constraints $$$n \leq 10^5$$$.

I will welcome any feedback. Coming next: popcount, bitsets, dp with bitmasks. I will also make a YT video on this. YT video link is at the top.

Part 2 link

  • Vote: I like it
  • +206
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Here's a trick question: how much is 1LL<<66?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Nasal demons

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Well, it's UB, what should I expect? My guess is $$$0$$$ on most machines, but let's hear what it is.

    Or are you saying it isn't UB?

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, it's UB. Not a question specifically for you, just anyone who doesn't have much experience with bitwise operations, because it's so counterintuitive.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +28 Vote: I do not like it

      I would expect to see 4 (at least if values are runtime and not known to compiler)

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      what do you mean by UB

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        google -> what is UB in programming?

        In computer programming, undefined behavior (UB) is the result of executing a program whose behavior is prescribed to be unpredictable, in the language specification to which the computer code adheres.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    I tried this code

    #include<iostream>
    int main(){
        for(int i = 62; i < 70; ++i){
            std::cout << "for i = " << i << " val = " << (1LL << i) << "\n";
        }
        std::cout << "For seperate i = 66 val = " << (1LL << 66) << "\n";
        return 0;
    } 
    

    It computes a non-zero value for shifting by i but computes 0 for shifting by constant

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah, undefined behaviour is undefined.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It will not be UB soon, since C++20.

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      source? I doubt they would go with such pessimization.
      according to cppreference (I know, it's not always correct ) there are changes in c++20 but still

      In any case, if the value of the right operand is negative or is greater or equal to the number of bits in the promoted left operand, the behavior is undefined.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You are right, I didn't see the restriction on the right operand.
        But it seems that now 8 << 30 will be defined (0), however 1 << 33 will remain undefined behaviour.

        The value of a << b is the unique value congruent to $$$a * 2^b$$$ modulo $$$2^N$$$ where N is the number of bits in the return type (that is, bitwise left shift is performed and the bits that get shifted out of the destination type are discarded).

        Mentioned here (in since C++20 section) https://en.cppreference.com/w/cpp/language/operator_arithmetic#Bitwise_shift_operators

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          8<<30 is plain signed overflow which you should avoid anyway, 8U<<30 was defined for a long time already. C++20 just makes the left shift an exception from the rule that signed overflow is UB.

»
4 years ago, # |
Rev. 2   Vote: I like it +15 Vote: I do not like it

When red's code is mask & (1 << i) instead of mask >> i & 1 ....

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    When you check the divisibility by $$$2$$$ with bitwise operations... Are you so sure that your method is simpler and easier to understand for beginners?

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it +29 Vote: I do not like it

      actually, point of my massage is about checking bits in long long mask

      beginners (and not so) very often making this mistake

      about understanding of methods — i think it same

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +26 Vote: I do not like it

        Ok, that's a good point. Well, you might need a power of two in your solution, so you need to know how to use 1LL << k anyway, what is mentioned in the article. Though, now I see the advantage of your method.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -6 Vote: I do not like it

      >beginner uses it with 64-bit bitmasks

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I do ((mask&(1<<i))!=0)

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      well, ok, but nowadays I believe reds use bitests

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I don't think that there's that much correlation between how someone codes and what rating he is. It's like 90% problem solving, 10% fast coding.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The introductory part might be a little confusing: you have ^ in your list of logical operators and again in your list of bitwise operators.

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    thanks, added a note for that

    EDIT: I modified that part more in response to a comment below.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It might be better to use ^^ to denote logical XOR and simply note that languages tend not to include it. I don't see that ^ is analogous to && and || the way you are listing things.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I think some think like if (a ^^ b) can be done with if (a ==! b) so they dont add the logical XOR ^^ in C++

»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Amazing Errichto waiting for dp with bitmasks.

»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

How soon can we expect the YT videos??

»
4 years ago, # |
  Vote: I like it +52 Vote: I do not like it

One quick shortcut for to_binary(num) while debugging is bitset<8>(num).
You can do cout << bitset<8>(num) << endl;

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you please explain me what is to_binary(num) please

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      expand this part in blog C++ code for experimenting

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It's my function from the blog, you can ignore it. Just remember that bitset<8>(x) will cast variable $$$x$$$ into bitset.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

//////please someone help me with this code of 1st problem, i am getting wrong answer at test case 21

include <bits/stdc++.h>

define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

define ll long long

using namespace std;

int main() { IOS; ll n,k,i,ans,x,s,mask,ch=0,r=0; cin>>n; vector v; for(i=0;i<n;i++){ cin>>x; ch+=x; v.push_back(x); } if(ch%360==0) cout<<"YES"<<endl; else if(ch%2==0){ ch/=2; for(mask=0;mask<(1LL<<n);mask++){ ans=0; for(i=0;i<n;i++){ if(mask & (1LL<<i)){ ans+=v[i]; } if(ans==ch) { cout<<"YES"<<endl; return 0; } }

}

cout<<"NO"<<endl;

} else{ cout<<"NO"<<endl; }

}

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Thanks for such an amazing blog. Special thanks to give additional links for problem to understand the concept clearly.

»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it

bitset<> when used in conversion to binary to decimal : cout<< bitset<8>("1001").to_ulong() << endl;

»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

$$$ O \left( \frac{n^2}{32} \right) = O(n^2)$$$, would be more correct to say $$$O \left(\frac{n^2}{\text{machine word}} \right)$$$.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone share more resources regarding bitwise manipulation?

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Looks like it can be used like a bitset or vector, etc.

access: (x & 1<<k) write 1: (x |= 1<<k) write 0: (x ^= 1<<k)

If I'm not mistaken...