Bit Positions problem from CodeEval explained

Recently I’ve been solving some problems from sites like usaco and CodeEval and I found this one in the “Easy” section! Well, this is actually a pretty easy problem to solve but some beginners might have some problems while solving this because it involves bitwise operators.

This is the problem description:

Challenge Description:

Given a number n and two integers p1,p2 determine if the bits in position p1 and p2 are the same or not. Positions p1,p2 and 1 based.

Input sample:

The first argument will be a text file containing a comma separated list of 3 integers, one list per line. e.g.

86,2,3
125,1,2

Output sample:

Print to stdout, ‘true'(lowercase) if the bits are the same, else ‘false'(lowercase).

e.g.

true
false

So, if you’re reading this your problem might be: How do I compare two bits of a number? It’s simple! Let’s take a look at the first example, the number 86.

Number 86 it’s represented in binary as: 1010110

You could have calculated this easily by hand, doing successives divisions by 2 until the quotient was 0.

86/2 = 43 (Remainder is 0)

43/2 = 21 (Remainder is 1 because 43/2 = 2 * 21 + 1, where 1 is the remainder)

21/2 = 10 (Remainder is 1)

10/2 = 5 (Remainder is 0)

5/2 = 2 (Remainder is 1)

2/2 = 1 (Remainder is 0)

1/2 = 0 (Remainder is 1)

So “join” the remainder from bottom to top and you have the binary representation of 86: 1010110

Now the most important question.. How do you compare two bits of a decimal number?

It’s simple, using the bitwise operators! For this what you want to do is a right shift! Let me explain this better:

Imagine for the first case where you want to compare the 2nd and the 3rd binary digit(bit) of the number 86

You already know that the answer is “true” because 1(2nd digit) is equal to 1(3rd digit).

Here it’s the magic formula:

((86 >> 1) & 1) == ((86 >> 2) & 1)


If this is true then the digits are equal, if not they’re not equal.

I’ll now explain how this is done:

For the 2nd digit we start by doing a right shift of 1(86 >> 1)

I used 1 for the 2nd digit because in the statement it says that both bits are 1 based.

Original number: 1010110

After (86 >> 1): 0101011

0101011 & 1 = 1 But why?

0101011

0000001

———-

0000001

With the AND operator the result is only 1 when both bits are 1!

Here it is the table:

0 0 Result: 0
0 1 Result: 0
1 0 Result: 0
1 1 Result: 1

For the second bit you do the same thing:

Original number: 1010110

After (86 >> 2): 0010101

0010101 & 1 = 1 for the same reason

0010101

0000001

———

0000001

1 == 1? Yes. So the answer is TRUE!

Here it is my poor C++(please go to here)

Anúncios

Posted on 21 de Agosto de 2013, in Sem categoria and tagged , , , , . Bookmark the permalink. 1 Comentário.

  1. This has to be the worst explained problem i have ever encountered. Great work deciphering it!

Deixe uma Resposta

Preencha os seus detalhes abaixo ou clique num ícone para iniciar sessão:

Logótipo da WordPress.com

Está a comentar usando a sua conta WordPress.com Terminar Sessão / Alterar )

Imagem do Twitter

Está a comentar usando a sua conta Twitter Terminar Sessão / Alterar )

Facebook photo

Está a comentar usando a sua conta Facebook Terminar Sessão / Alterar )

Google+ photo

Está a comentar usando a sua conta Google+ Terminar Sessão / Alterar )

Connecting to %s

%d bloggers like this: