PrevNext
Somewhat Frequent
 0/14

Intro to Bitwise Operators

Authors: Siyong Huang, Chongtian Ma, Mihnea Brebenel

Six bitwise operators and the common ways they are used.

Edit This Page
Resources
CPH
CF

Great explanation by Errichto

GFG

The same operators are used in java and python

At this point, you should already be familiar with the three main bitwise operators (AND, OR, and XOR). Let's take a look at some examples to better understand them.

Focus Problem – try your best to solve this problem before continuing!

Solution - Take a Guess

In fact, we can figure out the sum of two numbers using just their AND, OR and XOR values! Suppose we know their XOR values, we can use the following property:

a+b=2(a&b)+aba + b = 2 \cdot (a \& b) + a \oplus b

The proof is as follows:

aba \oplus b is essentially just a+ba + b in base 22 but we never carry over to the next bit. Recall a bit in aba \oplus b is 11 only if the bit in aa is different from the bit in bb, thus one of them must be a 11. However, when we add two 11 bits, we yield a 00, but we do not carry that 11 to the next bit. This is where a&ba \& b comes in.

a&ba \& b is just the carry bits themselves, since a bit is 11 only if it's a 11 in both aa and bb, which is exactly what we need. We multiply this by 22 to shift all the bits to the left by one, so every value carries over to the next bit.

To acquire the XOR values of the two numbers, we can use the following:

ab=¬(a&b)&(ab)a \oplus b = \lnot(a \& b) \& (a | b)

The proof is as follows:

Recall a bit in aba \oplus b is 11 only if the bit in aa is different from the bit in bb. By negating a&ba \& b, the bits that are left on are in the following format:

  • If it's 11 in aa and 00 in bb
  • If it's 00 in aa and 11 in bb
  • If it's 00 in aa and 00 in bb

Now this looks pretty great, but we need to get rid of the third case. By taking the bitwise AND with aba | b, the ones that are left on is only if there is a 11 in either aa or bb. Obviously, the third case isnt included in aba | b since both bits are off, and we successfully eliminate that case.

Now that we can acquire the sum of any two numbers in two queries, we can easily solve the problem now. We can find the values of the first three numbers of the array using a system of equations involving their sum (note n3n \geq 3). Once we have acquired their independent values, we can loop through the rest of the array.

C++

#include <bits/stdc++.h>
using namespace std;
int ask(string s, int a, int b) {
cout << s << ' ' << a << ' ' << b << endl;
int res;
cin >> res;
return res;
}

Java

import java.io.*;
import java.util.*;
public class TakeAGuess {
private static BufferedReader br =
new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws IOException {
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());

Python

def ask(s: str, a: int, b: int) -> int:
print(f"{s} {a} {b}", flush=True)
return int(input())
def sum(a: int, b: int) -> int:
""":return: the sum of the elements at a and b (0-indexed)"""
a += 1
b += 1
and_ = ask("and", a, b)

Example - Addition

Now let's take a look at implementing addition and multiplication using only bitwise operators. Before we do so, though, try implementing addition using bitwise operators on your own! You can test your implementation here.

Solution - Addition

If we perform addition without carrying, then we are simply performing the XOR (^) operator. Then, the bits that we carry over are those equivalent to 11 in both numbers: a&ba\&b.

C++

int add(int a, int b) {
while (b > 0) {
int carry = a & b;
a ^= b;
b = carry << 1;
}
return a;
}

Java

public static int add(int a, int b) {
while (b > 0) {
int carry = a & b;
a ^= b;
b = carry << 1;
}
return a;
}

Python

def add(a: int, b: int) -> int:
while b > 0:
carry = a & b
a ^= b
b = carry << 1
return a

Example - Multiplication

Now try implementing multiplication using bitwise operators! If you want to test your implementation of multiplication, you can do so here.

Solution - Multiplication

For simplicity, we will use the sum functions defined above. If we divide up bb into 2b1+2b2++2bn2^{b_1}+2^{b_2}+\dots+2^{b_n}, we get the following:

a×b=a×(2b1+2b2++2bn)=a2b1+a2b2++a2bn=bits in ba<<bi\begin{align*} &a \times b \\ &= a \times (2^{b_1}+2^{b_2}+\dots+2^{b_n}) \\ &= a2^{b_1}+a2^{b_2}+\dots+a2^{b_n} \\ &= \sum_{\text{bits in b}} {a\texttt{<<}b_i} \end{align*}

(This same idea is used in binary exponentiation!)

C++

int prod(int a, int b) {
int c = 0;
while (b > 0) {
if ((b & 1) == 1) {
c = add(c, a); // Use the addition function we coded previously
}
a <<= 1;
b >>= 1;
}
return c;
}

Java

public static int prod(int a, int b) {
int c = 0;
while (b > 0) {
if ((b & 1) == 1) {
c = add(c, a); // Use the addition function we coded previously
}
a <<= 1;
b >>= 1;
}
return c;
}

Python

def prod(a: int, b: int) -> int:
c = 0
while b > 0:
if b & 1:
c = add(c, a) # Use the addition function we coded previously
a <<= 1
b >>= 1
return c

XOR Operation

Perhaps one of the most common binary operations in practice is bitwise xor. The special property that differentiates it from the other bitwise operations is that xor is its own inverse, i.e. xx=0x \oplus x = 0.

Focus Problem – try your best to solve this problem before continuing!

Explanation

Let's analyze the bits of each xor-sum independently. In this case, we'll check for every bit position, i.e. for every power of two, whether or not it's set in the xor-sum of every contiguous subsequence. This way, we transformed the problem into counting the number of subsequences with non-zero xor-sum; this will be applied on the array form by the bits on the same position in all the values.

Implementation

Time Complexity: O(N)\mathcal{O}(N)

C++

#include <iostream>
#include <numeric>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> v(n);

Python

n = int(input())
v = list(map(int, input().split()))
res = 0
"""
For every bit position
check if it's set on in the xor-sum of every subsequence
"""
for i in range(30):
s = 0
StatusSourceProblem NameDifficultyTags
CFEasy
Show TagsBitwise, Greedy
CFEasy
Show TagsBitwise
CFEasy
Show TagsBinary Search, Bitwise, Complete Search
ACEasy
Show TagsBitwise
CFEasy
Show TagsBitwise, Sorting, Trie
SilverEasy
Show TagsBitwise, Complete Search
SilverNormal
Show TagsBitwise, Graphs
CFNormal
Show TagsBinary Search, Bitwise, Prefix Sums
CFNormal
Show TagsBitwise, Prefix Sums
CSESNormal
Show TagsBitwise, PIE
CFNormal
Show TagsGreedy, Math
CFHard
Show TagsInteractive, Math

Quiz

Which of the following will set the kth bit of int x as true? Assume you do not know what the value of the kth bit currently is.

Question 1 of 3

Module Progress:

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

PrevNext