Six bitwise operators and the common ways they are used.

Resources | ||||
---|---|---|---|---|

CPH | 10.2 - Bit Operations | |||

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 theirXOR values, we can use the following property:

$a + b = 2 \cdot (a \& b) + a \oplus b$a+b=2⋅(a&b)+a⊕b

The proof is as follows:

$a \oplus b$a⊕b is essentially just $a + b$a+b in base $2$2 but we never carry over to the next bit. Recall a bit in $a \oplus b$a⊕b is $1$1 only if the bit in $a$a is different from the bit in $b$b, thus one of them must be a $1$1. However, when we add two $1$1 bits, we yield a $0$0, but we do not carry that $1$1 to the next bit. This is where $a \& b$a&b comes in.

$a \& b$a&b is just the carry bits themselves, since a bit is $1$1 only if it's a $1$1 in both $a$a and $b$b, which is exactly what we need. We multiply this by $2$2 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:

$a \oplus b = \lnot(a \& b) \& (a | b)$a⊕b=¬(a&b)&(a∣b)

The proof is as follows:

Recall a bit in $a \oplus b$a⊕b is $1$1 only if the bit in $a$a is different from the bit in $b$b. By negating $a \& b$a&b, the bits that are left on are in the following format:

If it's $1$1 in $a$a and $0$0 in $b$b

If it's $0$0 in $a$a and $1$1 in $b$b

If it's $0$0 in $a$a and $0$0 in $b$b

Now this looks pretty great, but we need to get rid of the third case. By taking the bitwise AND with $a | b$a∣b, the ones that are left on is only if there is a $1$1 in either $a$a or $b$b. Obviously, the third case isnt included in $a | b$a∣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 $n \geq 3$n≥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 $1$1 inboth numbers: $a\&b$a&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$b$b into $2^{b_1}+2^{b_2}+\dots+2^{b_n}$2b1+2b2+⋯+2bn, we get the following:

$\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*}$a×b=a×(2b1+2b2+⋯+2bn)=a2b1+a2b2+⋯+a2bn=bitsinb∑a<<bi

(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 operation 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. $x \oplus x = 0$x⊕x=0.

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

### Explanation

Simulating the process, similarly to the Pascal's triangle, isn't efficient,because of $n$n being too large. One good practice when dealing with such problems is analyzing how the answer is affected by each single value. Keeping in mind that xor is itsown inverse, a value $x$x xored with itself an **even** number of times will result in $0$0, thus cancelling each other out; on the other hand, the value $x$x xoredwith itself and **odd** number of times will simply result in $x$x. Consequently, we can shift our focus to finding for each bottom value the number of times it will affectin the top value.

Let's take a look at how bottom values modify the final result.

As you can see, the value $B$B does not appear in the final result, thus it can be ignore. Additionally, the bottom row values inPascal's triangle of height five are: $1,4,6,4,1$1,4,6,4,1. We can think of these values as the number of occurrences of each bottom row value.In the above image, value $A$A will be xored one time in the result, while value $B$B will be xored four times in the result. Therefore,the parity of the frequency tells us that value $A$A contributes to the result, whil value $B$B is cancels out itself.

Because we are only interested in the parity of the binomial coefficient, there is no need of computing its actual value. We can simply check the parity bycounting the power of two in $\binom{n}{k}=\frac{n!}{k! \cdot (n-k)!}$(kn)=k!⋅(n−k)!n!. With this in mind, precompute $pref_i=p$prefi=p where $p$p is the power of two in $i!$i! factorization.Therefore, the binomial coefficient is odd if: $pref_n-pref_k-pref_{n-k}=0$prefn−prefk−prefn−k=0.

### Implementation

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

C++

#include <iostream>

#include <vector>

using namespace std;

int main() {

int n;

cin >> n;

vector<int> pref(n + 1);

for (int i = 2; i <= n; i++) {

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

CF | Easy | ## Show TagsBitwise, Greedy | |||

CF | Easy | ## Show TagsBitwise | |||

CF | Easy | ## Show TagsBinary Search, Bitwise, Complete Search | |||

AC | Easy | ## Show TagsBitwise | |||

CF | Easy | ## Show TagsBitwise, Sorting, Trie | |||

Silver | Easy | ## Show TagsBitwise, Complete Search | |||

Silver | Normal | ## Show TagsBitwise, Graphs | |||

CF | Normal | ## Show TagsBinary Search, Bitwise, Prefix Sums | |||

CF | Normal | ## Show TagsBitwise, Prefix Sums | |||

CSES | Normal | ## Show TagsBitwise, PIE | |||

CF | Normal | ## Show TagsGreedy, Math | |||

CF | Hard | ## 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