Bit Manipulation

forthright48 on August 31, 2015

On this post, we will look into how to use “Bitwise Operators” to manipulate bits of a number. Bit manipulation is a useful tool that can sometimes perform complicated tasks in a \simple manner.

We will work on integer values and assume each number has $32$ bits in them. If a number has only $0$ or $1$ as its digit, then assume that it is in binary form. All position of bits is $0$ indexed.

Since binary values can only be $0$ or $1$, we sometimes refer them like light bulbs. A bit being “Off” means it has value $0$ and being “On” means it has value $1$. Bit $1$ is also referred as “Set” and bit $0$ as “Reset”.

We need to have a strong grasp of how AND, OR, Negation, XOR and Shift Operators work to understand how bit manipulation works. If you have forgotten about them, then make sure you revise.

Checking Bit at Position X

Given a number $N$, find the value of its bit at position $X$. For example, if $N=12=(1100)_2$ and $X=2$, then value of bit is $1$.

So how do we find it? We can find this value in three steps:

  1. Let, $mask = 1 << X$
  2. Let, $res = N \ \& \ mask$
  3. If $res$ is $0$, then bit is $0$ at that position, else bit is $1$.

Let us see it in action with the example above, $N = 12$ and $X = 2$.

$1100$
$\underline{0100} \&$ ( $1 << 2$ is just $1$ shifted to left twice )
$0100$

Now, what happened here? In step $1$, when we left shifted $1$ $X$ times, we created a number $mask$ which has bit $1$ only at position $X$. This is a useful application of left shift operator. Using this, we can move $1$ bit anywhere we want.

Next, at step $2$, we find the result of performing AND operator between $N$ and $mask$. Since $mask$ has $0$ in all positions except $X$, the result will have $0$ in all places other than $X$. That’s because performing AND with $0$ will always give $0$. Now, what about position $X$. Will the result at position $X$ have $0$ too? That depends on the bit of $N$ at position $X$. Since, the $X$ bit in the mask is $1$, the only way result will have $0$ at that position if $N$ has $0$ in that position.

So, when all position of $res$ is $0$, that is $res$ has value $0$, we can say that $N$ has $0$ bit in position $X$, otherwise it doesn’t.

Set Bit at Position $X$

Given a value $N$, turn the bit at position $X$ of $N$ to $1$. For example, $N=12=1100$ and $X=0$, then $N$ will become $13=1101$.

This can be done in two steps:

  1. Let, $mask = 1 << X$
  2. $N = N \ | \ mask$

$1100$
$\underline{0001} \ |$
$1101$

In step $1$, we shift a $1$ bit to position $X$. Then we perform OR between $N$ and $mask$. Since $mask$ has 0 in all places except $X$, in the result, all those places remain unchanged. But $mask$ has $1$ in position $X$, so in result position $X$ will be $1$.

Reset Bit at Position $X$

Given a value $N$, turn the bit at position $X$ of $N$ to $0$. For example, $N=12=1100$ and $X=3$, then $N$ will become $4=0100$.

This cane be done in three steps:

  1. Let, $mask = 1 << X$
  2. $mask = \sim mask$
  3. $N = N \ \& \ mask$

$1100$
$\underline{0111} \ \&$ ( We first got $1000$ from step $1$. Then used negation from step 2.)
$0100$

In step $1$ we move $1$ bit to position $X$. This gives us a number of $1$ in position $X$ and $0$ in all other places. Next, we negate the $mask$. This flips all bits of $mask$. So now we have $0$ in position $X$ and $1$ in all other places. Now when we perform AND between $mask$ and $N$, it forces the bit at the $X$ position to $0$ and all other bits stay intact.

Toggle Bit at Position X

Given a value $N$, toggle the bit at position $X$, i.e if the bit at $X$ is $0$ then make it $1$ and if it is already $1$, make it $0$.

This can be done in two steps:

  1. Let, $mask = 1 << X$
  2. $N = N \ \wedge \ mask$

First, we shift bit $1$ to our desired position $X$ in step $1$. When XOR is performed between a bit and $0$, the bit remains unchanged. But when XOR performed between a bit and $1$, it toggles. So all position except $X$ toggles during step 2, since all position in mask except $X$ is $0$.

Coding Tips

When coding these in C++, make sure you use lots of brackets. Bitwise operators have lower precedence than $==$ and $!=$ operator which often causes trouble. See here.

What would be the output of this code:

if ( 0 & 6 != 7 ) printf ( "True\n" );
else printf ( "False\n" );

You might expect things to follow this order: $0 \ \& \ 6 = 0$ and $0 \ \neq 7$, so “True” will be output. But due to precedence of operators, the output comes out “False”. First $6 \ != 7$ is checked. This is true, so $1$ is returned. Next $0 \ \& \ 1$ is performed which is $0$.

The best way to avoid these kind of mishaps is to use brackets whenever you are using bitwise operators. The correct way to write the code above is:

if ( (0 & 6) != 7 ) printf ( "True\n" );
else printf ( "False\n" );

This prints “True” which is our desired result.

Conclusion

These are the basics of bit manipulation and by no means the end of it. There are lots of other tricks that are yet to be seen, such as “Check Odd or Even”, “Check Power of Two”, “Right Most Bit”. We will look into them some other day.

Reference

  1. forthright48 – Bitwise Operators
  2. CPPReference – C++ Operator Precedence

Bitwise Operators

forthright48 on August 27, 2015

We know about arithmetic operators. The operators $+,-,/$ and $\times$ adds, subtracts, divides and multiplies respectively. We also have another operator $\%$ which finds the modulus.

Today, we going to look at $6$ more operators called “Bitwise Operators”. Why are they called “Bitwise Operators”? That’s because they work using the binary numerals (bits, which are the individual digits of the binary number) of their operands. Why do we have such operators? That’s because in computers all information is stored as strings of bits, that is, binary numbers. Having operators that work directly on them is pretty useful.

We need to have a good idea how Binary Number System works in order to understand how these operators work. Read more on number system in [ref1] Introduction to Number Systems. Use the $decimalToBase()$ function from [ref1] to convert the decimal numbers to binary and see how they are affected.

Bitwise AND ($\&$) Operator

The $\&$ operator is a binary operator. It takes two operands and returns a single integer as the result. Here is how it affects the bits.

$0 \ \& \ 0 = 0$
$0 \ \& \ 1 = 0$
$1 \ \& \ 0 = 0$
$1 \ \& \ 1 = 1$

It takes two bits and returns another bit. The $\&$ operator will take two bits $a, b$ and return $1$ only if both $a$ AND $b$ are $1$. Otherwise, it will return $0$.

But that’s only for bits. What happens when we perform a $\&$ operation on two integer number?

For example, what is the result of $A \ \& \ B$ when $A = 12$ and $B = 10$?

Since $\&$ operator works on bits of binary numbers we have to convert $A$ and $B$ to binary numbers.

$A = (12)_{10} = (1100)_2$
$B = (10)_{10} = (1010)_2$

We know how to perform $\&$ on individual bits, but how do we perform $\&$ operation on strings of bits? Simple, take each position of the string and perform and operations using bits of that position.

$1100$
$\underline{1010} \ \&$
$1000$

Therefore, $12 \ \& \ 10 = 8$.

In C++, it’s equivalent code is:

printf ("%d\n", 12 & 10 );

Bitwise OR ($|$) Operator

The $|$ operator is also a binary operator. It takes two operands and returns single integer as the result. Here is how it affects the bits:

$0 \ | \ 0 = 0$
$0 \ | \ 1 = 1$
$1 \ | \ 0 = 1$
$1 \ | \ 1 = 1$

The $|$ operator takes two bits $a, b$ and return $1$ if $a$ OR $b$ is $1$. Therefore, it return $0$ only when both $a$ and $b$ are $0$.

What is the value of $A|B$ if $A=12$ and $B=10$? Same as before, convert them into binary numbers and apply $|$ operator on both bits of each position.

$1100$
$\underline{1010} \ |$
$1110$

Therefore $12|10 = 14$.

printf ( "%d\n", 12 | 10 );

Bitwise XOR ($\wedge$) Operator

Another binary operator that takes two integers as operands and returns integer. Here is how it affects two bits:

$0 \ \wedge \ 0 = 0$
$0 \ \wedge \ 1 = 1$
$1 \ \wedge \ 0 = 1$
$1 \ \wedge \ 1 = 0$

XOR stands for Exclusive-OR. This operator returns $1$ only when both operand bits are not the same. Otherwise, it returns $0$.

What is the value of $A \wedge B$ if $A=12$ and $B=10$?

$1100$
$\underline{1010} \ \wedge$
$0110$

Therefore, $12 \wedge 10 = 6$.

In mathematics, XOR is represented with $oplus $, but I used $\wedge$ cause in C++ XOR is performed with $\wedge$.

printf ( "%d\n", 12 ^ 10 );

Bitwise Negation ($\sim$) Operator

This is a unary operator. It works on a single integer and flips all its bits. Here is how it affects individual bits:

$\sim \ 0 = 1$
$\sim \ 1 = 0$

What is the value of $\sim A$ if $A = 12$?

$\sim \ (1100)_2 = (0011)_2 = (3)_{10}$

But this will not work in code cause $12$ in C++ is not $1100$, it is $0000…1100$. Each integer is $32$ bits long. So when each of the bits of the integer is flipped it becomes $11111…0011$. If you don’t take an unsigned int, the value will even come out negative.

printf ( "%d\n", ~12 );

Bitwise Left Shift ($<<$) Operator

The left shift operator is a binary operator. It takes two integers $a$ and $b$ and shifts the bits of $a$ towards LEFT $b$ times and adds $b$ zeroes to the end of $a$ in its binary system.

For example, $(13)_{10} << 3 = (1101)_2 << 3 = (1101000)_2$.

Shifting the bits of a number $A$ left once is the same as multiplying it by $2$. Shifting it left three times is the same as multiplying the number by $2^3$.

Therefore, the value of $A << B = A \times 2^B$.

printf ( "%d\n", 1 << 3 );

Bitwise Right Shift ($>>$) Operator

The $>>$ Operator does opposite of $<<$ operator. It takes two integer $a$ and $b$ and shifts the bits of $a$ towards RIGHT $b$ times. The rightmost $b$ bits are lost and $b$ zeroes are added to the left end.

For example, $(13)_{10} >> 3 = (1101)_2 >> 3 = (1)_2$.

Shifting the bits of a number $A$ right once is the same as dividing it by $2$. Shifting it right three times is the same as dividing the number by $2^3$.

Therefore, the value of $A >> B = \lfloor \frac{A}{2^B} \rfloor$.

printf ( "%d\n", 31 >> 3 );

Tips and Tricks

  1. When using $<<$ operator, careful about overflow. If $A << B$ does not fit into $int$, make sure you type cast $A$ into long long. Typecasting $B$ into long long does not work.
  2. $A \ \& \ B \leq MIN(A,B)$
  3. $A \ | \ B \geq MAX(A,B)$

Conclusion

That's all about bitwise operations. These operators will come useful during "Bits Manipulation". We will look into it on next post.

Resource

    1. forthright48 - Introduction to Number Systems
    1. Wiki - Bitwise Operation

SPOJ LCMSUM – LCM Sum

forthright48 on August 27, 2015

Problem

Problem Link – SPOJ LCMSUM

Given $n$, calculate the sum $LCM(1,n) + LCM(2,n) + … + LCM(n,n)$, where $LCM(i,n)$ denotes the Least Common Multiple of the integers $i$ and $n$.

Solution

I recently solved this problem and found the solution really interesting. You can find the formula that solves this problem on OEIS. I will show you the derivation here.

In order to solve this problem, you need to know about Euler Phi Function, finding Divisor using Sieve and some properties of LCM and GCD.

Define SUM

Let us define a variable SUM which we need to find.

$SUM = LCM(1,n) + LCM(2,n) + … + LCM(n,n)$ (take $LCM(n,n)$ to the other side for now )
$SUM – LCM(n,n) = LCM(1,n) + LCM(2,n) + … + LCM(n-1,n)$

We know that $LCM(n,n) = n$.

$SUM – n = LCM(1,n) + LCM(2,n) + … + LCM(n-1,n)$ ($eq 1$)

Reverse and Add

$SUM – n = LCM(1,n) + LCM(2,n) + … + LCM(n-1,n)$ (Reverse $eq 1$ to get $eq 2$)
$SUM – n = LCM(n-1,n) + LCM(n-2,n) + … + LCM(1,n)$ ( $eq 2$ )

No what will we get if we add $eq 1$ with $eq 2$? Well, we need to do more work to find that.

Sum of $LCM(a,n) + LCM(n-a,n)$

$x = LCM(a,n) + LCM(n-a,n)$
$x = \frac{an}{gcd(a,n)} + \frac{(n-a)n}{gcd(n-a,n)}$ ($eq 3$)

Arghh. Now we need to prove that $gcd(a,n)$ is equal to $gcd(n-a,n)$.

If $c$ divides $a$ and $b$, then, $c$ will divide $a+b$ and $a-b$. This is common property of division. So, if $g = gcd(a,n)$ divides $a$ and $n$, then it will also divide $n-a$. Hence, $gcd(a,n)=gcd(n-a,n)$.

So $eq 3$ becomes:

$x = \frac{an}{gcd(a,n)} + \frac{(n-a)n}{gcd(a,n)}$
$x = \frac{an + n^2 -an}{gcd(a,n)}$.
$x = \frac{n^2}{gcd(a,n)}$.

Now, we can continue adding $eq 1$ with $eq 2$.

Reverse and Add Continued

$SUM – n = LCM(1,n) + LCM(2,n) + … + LCM(n-1,n)$ ($eq 1$)
$SUM – n = LCM(n-1,n) + LCM(n-2,n) + … + LCM(1,n)$ ( $eq 2$ Add them )$2(SUM-n)= \frac{n^2}{gcd(1,n)} + \frac{n^2}{gcd(2,n)} + … \frac{n^2}{gcd(n-1,n)}$
$2(SUM-n ) = \sum_{i=1}^{n-1}\frac{n^2}{gcd(i,n)}$
$2(SUM-n ) = n\sum_{i=1}^{n-1}\frac{n}{gcd(i,n)}$ ( take $n$ common )

Group Similar GCD

What are the possible values of $g = gcd(i,n)$? Since $g$ must divide $n$, $g$ needs to be a divisor of $n$. So we can list the possible values of $gcd(i,n)$ by finding the divisors of $n$.

Let $Z = n\sum_{i=1}^{n-1}\frac{n}{gcd(i,n)}$. Now, every time $gcd(i,n) = d$, where $d$ is a divisior of $n$, $n \times \frac{n}{d}$ is added to $Z$. Therefore, we just need to find, for each divisor $d$, how many times $n \times \frac{n}{d}$ is added to $Z$.

How many values $i$ can we put such that $gcd(i,n) = d$? There are $\phi(\frac{n}{d})$ possible values of $i$ for which we get $gcd(i,n)=d$. Therefore:

$2(SUM-n ) = n\sum_{i=1}^{n-1}\frac{n}{gcd(i,n)}$
$2(SUM-n ) = n\sum_{d |n, d \neq n } \phi(\frac{n}{d}) \times \frac{n}{d}$ (but, $\frac{n}{d}$ is also a divisor of $n$ )
$2(SUM-n ) = n\sum_{d |n, d \neq 1 } \phi(d) \times d$ ( when $d = 1$, we get $\phi(1)times 1$ )
$2(SUM-n ) = n( \sum_{d |n } ( \phi(d) \times d ) -1 )$
$2(SUM-n ) = n \sum_{d |n } (\phi(d) \times d ) – n$
$2SUM – 2n + n = n\sum_{d |n } \phi(d) \times d$
$2SUM – n = n\sum_{d |n } \phi(d) \times d$

$$2SUM = n( \sum_{d |n } \phi(d) \times d )+ n \\
2SUM = n ( \sum_{d |n } ( \phi(d) \times d ) + 1 ) \\
\therefore SUM = \frac{n}{2} ( \sum_{d |n } ( \phi(d) \times d ) + 1 )$$

Using this formula we can solve the problem.

Code


#include <bits/stdc++.h>

#define FOR(i,x,y) for(vlong i = (x) ; i <= (y) ; ++i)

using namespace std;
typedef long long vlong;

vlong res[1000010];
vlong phi[1000010];

void precal( int n ) {
    // Calculate phi from 1 to n using sieve
    FOR(i,1,n) phi[i] = i;
    FOR(i,2,n) {
        if ( phi[i] == i ) {
        for ( int j = i; j <= n; j += i ) {
            phi[j] /= i;
            phi[j] *= i - 1;
        }
    }
 }

 // Calculate partial result using sieve
 // For each divisor d of n, add phi(d)*d to result array
 FOR(i,1,n){
    for ( int j = i; j <= n; j += i ) {
        res[j] += ( i * phi[i] );
    }
 }
}

int main () {
    precal( 1000000 );

    int kase;
    scanf ( "%d", &kase );

    while ( kase-- ) {
        vlong n;
        scanf ( "%lld", &n );

        // We already have partial result in res[n]
        vlong ans = res[n] + 1;
        ans *= n;
        ans /= 2;

        printf ( "%lld\n", ans );
    }

    return 0;
}

We need to precalculate partial result using a sieve for all values of $N$. Precalculation has a complexity of $O(N \ ln(N))$. After pre-calculation, for each $N$ we can answer in $O(1)$.

Reference

  1. OEIS - A051193