bit bashing

[Rohit kumar Chandel]

Here is a small piece of program(again just 14 lines of program) which
counts the number of bits set in a number.

Input
Output

0
0(0000000)

5
2(0000101)

7
3(0000111)


int CountBits (unsigned int x )
{
static unsigned int mask[] = { 0x55555555,
0x33333333,
0x0F0F0F0F,
0x00FF00FF,
0x0000FFFF

} ;

int i ;
int shift ; /* Number of positions to shift to right*/

for ( i =0, shift =1; i < 5; i ++, shift *= 2)
x = (x & mask[i ])+ ( ( x >> shift) & mask);
return x;
}

Find out the logic used in the above program.

 

[jacob navia]

Rohit kumar Chandel wrote:

Do your own homework, or give us the address of your
teacher. We will send him the answer directly

 

[Mark Bluemel]

Here is a small piece of program(again just 14 lines of program)
....

Find out the logic used in the above program.

This smells like homework to me... I haven't done homework in over 30
years - why should I do yours?

 

[Rohit kumar Chandel]

Rohit kumar Chandel wrote:

Do your own homework, or give us the address of your
teacher. We will send him the answer directly

This is not a homework question. I have tried to understand the logic but
could not get it.
This is a piece of code which came to me from my friend as a puzzle. I
generally calculate number of bits set like this:

int CountBits(unsigned int x)
{
int count=0;
while(x)
{
count++;
x = x&(x-1);
}
return count;
}
which is much simpler.

Now can I get an answer, or still you need address for my teacher

Regards
Rohit

 

[Ian Collins]

Here is a small piece of program(again just 14 lines of program) which
counts the number of bits set in a number.

Input
Output

0
0(0000000)

5
2(0000101)

7
3(0000111)


int CountBits (unsigned int x )
{
static unsigned int mask[] = { 0x55555555,
0x33333333,
0x0F0F0F0F,
0x00FF00FF,
0x0000FFFF

} ;

int i ;
int shift ; /* Number of positions to shift to right*/

for ( i =0, shift =1; i < 5; i ++, shift *= 2)
x = (x & mask[i ])+ ( ( x >> shift) & mask);
return x;
}

Find out the logic used in the above program.

Write the bit patterns down on paper and run the loop to see what each
step does.

 

[Mark Bluemel]

Now can I get an answer, or still you need address for my teacher

That sort of attitude, together with the way you phrased your initial
query, is not the best way to get help.

 

[Mark Bluemel]

Write the bit patterns down on paper and run the loop to see what each
step does.

What? Use paper and a pen and a brain? Surely the net has made all that
redundant?

 

[Willem]

Rohit wrote:
) Here is a small piece of program(again just 14 lines of program) which
) counts the number of bits set in a number.
)
) <snip>

I'll give you a hint:
The code uses a crude form of SIMD-processing.
SIMD is 'Single Instruction, Multiple Data'.

To understand SIMD, here's a small puzzle for you:

Suppose you have a hand calculator, which can use up to 10 digits.
You have four numbers, a, b, c and d. Those numbers all have four
digits. Now, you have to calculate a+b and also c+d, but you're not
allowed to hit the '+' and the '=' button more than once, and you can't
use any other buttons (besides the 0-9 to enter the 4 numbers).

Now, if you can do that, try to add 5 sets of 1-digit numbers in one go.


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

 

[Kaz Kylheku]

This is not a homework question. I have tried to understand the logic but
could not get it.

So what do you want anyone else to do about it? The code is in front
of your eyes. Understanding it is your problem.

Have you tried, using a pencil-and-paper approach, stepping through
the code, for various input values?

By exactly what means do you think understanding will occur?

Do you think you can somehow magically understand a step-by-step
detailed process without understanding every individual step? How will
understanding leap from the printed page into your head?

How about unrolling the loop: it has a fixed number of iterations,
since i goes from 0 to 4, and shift goes through the sequence 1, 2, 4,
8, and 16, regardless of the input. So the calculation has five fixed
stages, which have been rolled up into a loop for brevity. These five
stages limit it to counting up to 32 bits (2 to the power of 5). At
each stage, the following is evaluated:

x = (x & mask) + ((x >> shift) & mask);

The initial input value x is the word whose bits are to be counted,
and the output of each stage is fed as input to the next stage. I.e.
each stage does this:

x = F_i(x)

Where F_i is a function of x specific to stage i. Each F_i is
characterized by choice of mask and shift value. So the five stages
are basically:

count = F_4(F_3(F_2(F_1(F_0(x)))))

the chained application of five functions. Based on this, you should
be able to draw these stages as one big flow diagram (even down to the
detail of a combinatorial circuit).

Start with the abstracted version.

x ---- F_0 -- F_1 -- F_2 -- F_3 -- F_4 ----- count

Now zoom in on the F's and draw out how they work. What is F_0? It is
this:

F_0(x) = x & mask_0 + (x >> shift_0) & mask_0

where mask_0 is 0x55555555 and shift_0 is 1. So in other words:

F_0(x) = x & 0x55555555 + (x >> 1) & 0x55555555;

At the bit level, 0x33333333 is the bit pattern 0101010101010101. What
is going on in this expression? The left side of the + selects all of
the even bits in the input word x. The right side, selects all of the
odd bits, but shifts them one position to the right. Let's give letter
names to the 32 bits, using upper case for the lower 16:

let x = abcd efgh ijkl mnop ABCD EFGH IJKL MNOP

What is x & 01010101010101010101010101010101? To make it clearer,
let's use the underscore character to represent zero. When we bitwise-
and x with the 0x5555... bit pattern, we get:

_b_d _f_h _j_l _n_p _B_D _F_H _J_L _N_P

What about the right side? If we shift x one bit to the right, we get:

_abc defg hijk lmno pABC DEFG HIJK LMNO

The P bit falls off, and a zero is shifted in. What happens when we
and this with 0x5555...?

_a_c _e_g _i_k _m_o _A_C _E_G _I_K _M_O

And now these two quantities are added together, like this:

_b_d _f_h _j_l _n_p _B_D _F_H _J_L _N_P
+ _a_c _e_g _i_k _m_o _A_C _E_G _I_K _M_O

Note how there are zeros in every other column. These zeros mean that
there is no carry in the addition. For instance if adding P and O in
the least significant bit column produces a carry bit, that carry bit
will add to the two zeros in the second column. There will be no
further carry into the third column. So essentially, this addition is
really 16 independent additions withiin the 32 bit word, namely

_b _d _f
+ _a + _c +_e .... and so on

Do you see what is going on? The bits are being added together
pairwise to produce 16 partial results of two bits each:

bits 30 and 31: (a + b)
bits 28 and 29: (c + d)
bits 26 and 27: (e + f)

and so on.

In the next stage, the same pattern is repeated, but it's widened to a
two bit addition producing a four bit result. The masking pattern is
0x3333 which is 001100110011, and the shift is two. It pairs the two
bit groups together and adds them.

bits 28-31: ((a + b) + (c + d))
bits 24-27: ((e + f) + (g + h))

Ultimately, this process will yield the sum:

a + b + c + d + e + ... + p + A + B + ... + P

And this sum is, of course, the number of bits in the original word,
since each letter represents a bit, 0 or 1. The algorithm exploits the
ability of the machine to manipulate word quantities in order to
partially parallelize this addition.

That's approximately how you understand something. The level of detail
you have to go in drawing it out depends on your experience and mental
power. Someone very intelligent or experienced or both will recognize
the pattern instantly and just see what is going on without having to
write out the process.

 

[Peter Nilsson]

[snipped by Jacob.]

Do your own homework, or give us the address of your
teacher. We will send him the answer directly

This is not a homework question.

It's a question you've chosen to try to answer, for the
purposes of education. You may not be doing it at home,
but to all intents and purposes, it is homework.

I have tried to understand the logic but could not get it.

Show us what you do understand. Demonstrate that you have
actually tried to solve the problem as you claim. Just
posting the question verbatim and asking others to solve
it is not likely to get you answers.

This is a piece of code which came to me from my friend
as a puzzle.

So it's homework.

I generally calculate number of bits set like this:

int CountBits(unsigned int x)
  {
      int count=0;
      while(x)
      {
          count++;
          x = x&(x-1);
      }
      return count;
  }
which is much simpler.

Good. That doesn't show you've analysed the original code,
but it indicates that you understand some elements of C.

Now can I get an answer, or still you need address for
my teacher

No. Quite apart from the fact that you could google for
bit count and find an explanation, you still haven't shown
your attempts to deconstruct the problem and solve it for
yourself.

As a former tutor, I've never had a problem with people
asking stupid questions, but I've never tolerated people
who just sit there and go "I don't know how to do it,"
without even trying.

You may well have attempted to analyse the code, but from
our point of view, there is no evidence of that. We can't
see your computer, your desk, or read your mind. All we
have is what you post. And your post sucked... ;-)

 

[Rohit kumar Chandel]

This is not a homework question. I have tried to understand the logic but
could not get it.

So what do you want anyone else to do about it? The code is in front
of your eyes. Understanding it is your problem.

Have you tried, using a pencil-and-paper approach, stepping through
the code, for various input values?

By exactly what means do you think understanding will occur?

Do you think you can somehow magically understand a step-by-step
detailed process without understanding every individual step? How will
understanding leap from the printed page into your head?

How about unrolling the loop: it has a fixed number of iterations,
since i goes from 0 to 4, and shift goes through the sequence 1, 2, 4,
8, and 16, regardless of the input. So the calculation has five fixed
stages, which have been rolled up into a loop for brevity. These five
stages limit it to counting up to 32 bits (2 to the power of 5). At
each stage, the following is evaluated:

x = (x & mask) + ((x >> shift) & mask);

The initial input value x is the word whose bits are to be counted,
and the output of each stage is fed as input to the next stage. I.e.
each stage does this:

x = F_i(x)

Where F_i is a function of x specific to stage i. Each F_i is
characterized by choice of mask and shift value. So the five stages
are basically:

count = F_4(F_3(F_2(F_1(F_0(x)))))

the chained application of five functions. Based on this, you should
be able to draw these stages as one big flow diagram (even down to the
detail of a combinatorial circuit).

Start with the abstracted version.

x ---- F_0 -- F_1 -- F_2 -- F_3 -- F_4 ----- count

Now zoom in on the F's and draw out how they work. What is F_0? It is
this:

F_0(x) = x & mask_0 + (x >> shift_0) & mask_0

where mask_0 is 0x55555555 and shift_0 is 1. So in other words:

F_0(x) = x & 0x55555555 + (x >> 1) & 0x55555555;

At the bit level, 0x33333333 is the bit pattern 0101010101010101. What
is going on in this expression? The left side of the + selects all of
the even bits in the input word x. The right side, selects all of the
odd bits, but shifts them one position to the right. Let's give letter
names to the 32 bits, using upper case for the lower 16:

let x = abcd efgh ijkl mnop ABCD EFGH IJKL MNOP

What is x & 01010101010101010101010101010101? To make it clearer,
let's use the underscore character to represent zero. When we bitwise-
and x with the 0x5555... bit pattern, we get:

_b_d _f_h _j_l _n_p _B_D _F_H _J_L _N_P

What about the right side? If we shift x one bit to the right, we get:

_abc defg hijk lmno pABC DEFG HIJK LMNO

The P bit falls off, and a zero is shifted in. What happens when we
and this with 0x5555...?

_a_c _e_g _i_k _m_o _A_C _E_G _I_K _M_O

And now these two quantities are added together, like this:

_b_d _f_h _j_l _n_p _B_D _F_H _J_L _N_P
+ _a_c _e_g _i_k _m_o _A_C _E_G _I_K _M_O

Note how there are zeros in every other column. These zeros mean that
there is no carry in the addition. For instance if adding P and O in
the least significant bit column produces a carry bit, that carry bit
will add to the two zeros in the second column. There will be no
further carry into the third column. So essentially, this addition is
really 16 independent additions withiin the 32 bit word, namely

_b _d _f
+ _a + _c +_e .... and so on

Do you see what is going on? The bits are being added together
pairwise to produce 16 partial results of two bits each:

bits 30 and 31: (a + b)
bits 28 and 29: (c + d)
bits 26 and 27: (e + f)

and so on.

In the next stage, the same pattern is repeated, but it's widened to a
two bit addition producing a four bit result. The masking pattern is
0x3333 which is 001100110011, and the shift is two. It pairs the two
bit groups together and adds them.

bits 28-31: ((a + b) + (c + d))
bits 24-27: ((e + f) + (g + h))

Ultimately, this process will yield the sum:

a + b + c + d + e + ... + p + A + B + ... + P

And this sum is, of course, the number of bits in the original word,
since each letter represents a bit, 0 or 1. The algorithm exploits the
ability of the machine to manipulate word quantities in order to
partially parallelize this addition.

That's approximately how you understand something. The level of detail
you have to go in drawing it out depends on your experience and mental
power. Someone very intelligent or experienced or both will recognize
the pattern instantly and just see what is going on without having to
write out the process.

Thanks a lot for understanding and answering my query. I had tried to solve
this problem on my own before posting it on the group. Since the loop is
just five stages deep, first thing I did was to unroll and find value of x
at each iteration. And at the end I was correctly getting the sum (equal to
number of bits set in word). But even after drawing it out I was not able to
get logic behind it.

The problem involves understanding the patterns not the bitwise maths. And
as pointed out by you a person must have a level of experience and
intelligence to understand them. I do not have any experience with such
patterns. And I knew that problem involves any such patterns. So I needed
help to add this snippet to my bag of tricks.

But people in group started to talk rubbish about the problem. I guess
partly because I did not provide the details of my attempt to solve the
problem.

Anyways my next question: Every now and then I come across snippets like the
one discussed here. These involve tricks based on patterns and exploiting
some of C constructs. Could anybody suggest any standard reading material on
this.

 

[santosh]

Rohit kumar Chandel wrote:

Anyways my next question: Every now and then I come across snippets
like the one discussed here. These involve tricks based on patterns
and exploiting some of C constructs. Could anybody suggest any
standard reading material on this.

Nothing other than a few years of experience programming and reading
other people's code will help you assimilate these type of constructs.
Of course a sound knowledge of the fundamentals is, without a question,
mandatory.

But beware that quite a lot of code on the Net makes many non-portable
assumptions and some of it is broken outright. That is precisely where
this group can help, since there are many here who know Standard C like
the back of their hand. While using non-portable code is often
necessary, it's always better to understand *why* you are using it in
the first place, and that implies that you understand the limitations
of Standard C.

<http://www.snippets.org/>

 

[Randy Howard]

Anyways my next question: Every now and then I come across snippets like the
one discussed here. These involve tricks based on patterns and exploiting
some of C constructs. Could anybody suggest any standard reading material on
this.

"exploiting" is probably too strong a word. It's merely using the
language features to take advantage of things you can do with simple
mathematics and/or boolean logic.

Here is a source of example, with the added bonus that the author
claims he will pay a cash reward for bug reports.
http://graphics.stanford.edu/~seander/bithacks.html

The book Hacker's Delight by Henry S. Warren (Addison-Wesley) is also
quite good. Additional information and errata can be found here:
http://www.hackersdelight.org/

 

[Nick Keighley]

At the bit level, 0x33333333 is the bit pattern 0101010101010101.

 

[Willem]

Rohit wrote:
) Anyways my next question: Every now and then I come across snippets like the
) one discussed here. These involve tricks based on patterns and exploiting
) some of C constructs. Could anybody suggest any standard reading material on
) this.

This particular trick actually doesn't have that much to do with
exploiting C constructs. The real basis of the trick is SIMD.
(Single Instruction Multiple Data).

What this means is that you can do multiple operations in parallel,
using just a single instruction. Addition is a prime example.

I'll try to demonstrate how to try this out yourself with a calculator.
(I posted this as a puzzle earlier in the thread, by the way).

Suppose we want to add 2347 to 1276, and at the same time add 8975 to 6532.
You can only use the '+' key one time, (and the '=' key once at the end).

You may want to try this out for yourself before reading on.




What you do is the following:

You type: aaaa0bbbb + cccc0dddd =

So, in our case, you type 234708975 + 127606532 =

The calculator responds with: 362315507.
You may note that 2347+1276=3623, and 8975+6532=15507.

The same trick can be done to add 4 1-digit numbers in one go:
You type a0b0c0d + e0f0g0h =

For example: 4020607 + 2070409 = 6091016. 4+2=6, 2+7=9, 6+4=10, 7+9=16


Now, to apply this trick to the problem of adding all digits in a number:

Suppose we want to know the sum of all digits in a number.
Let's take 97234923 as a random example.

First, we split it into two groups, masking out the even digits in one
group, and the odd digits in the other:

90204020 and 07030904

Then, shift the digits on the left side, and add the two numbers:

9020402 + 7030904 = 16051306 (9+7=16, 2+3=5, 4+9=13, 2+4=6)

Now, we have four two-digit numbers that we want to add, so we separate
again:

16001300 and 00050006

Shift the digits on the left side, and add the numbers:

160013 + 050006 = 210019 (16+5=21, 13+6=19)

And again:

210000 and 000019

becomes:
21 + 19 = 40

And there we have the total sum of the digits.


You can do the same trick with multiplication, but you have
to leave more room inbetween the digits:

Suppose you have four digits, a b c and d.
If you calculate a0b * c000d, the result will be:
ffgghhii, where ff = a*c, gg=b*c, hh=a*d and ii=b*d.
So that's four multiplications in a single go.


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

 

[Kaz Kylheku]

[snip]
And now these two quantities are added together, like this:

   _b_d _f_h _j_l _n_p _B_D _F_H _J_L _N_P
+  _a_c _e_g _i_k _m_o _A_C _E_G _I_K _M_O

Goofball, why are you using Outlook Express to post news? Look, it's
not able to quote an article properly? There is no separation between
what I wrote (that you quoted) and your own text.

You want to be a hacker, and you can't even find the right software
package to talk to a new server.

The problem involves understanding the patterns not the bitwise maths.

No, understanding this problem involves tracing the actual bitwise
math: what happens to every single bit of every operand.

When I gave a symbolic name (abdef ....) to every single bit in the
input, and traced what happens to it using the symbolic names, the
pattern emerged quite easily.

There are situations where that won't be true, like if the program
depends on some more advanced mathematics, such as obscure number-
theoretic properties of integers. But this isn't such a situation.

as pointed out by you  a person must have a level of experience and
intelligence to understand them.

No; what I pointed out is that intelligence and experience sometimes
let you skip some of these mundane pencil-and-paper steps (not because
you actually skip them, but because you're able to visualize them).
The pattern emerges after the visualizing or penciling (i.e. putting
in the work), not before.

I do not have any experience with such
patterns.

You're just too lazy to draw out what happens to every bit, and how it
contributes to the final result, just like you're too lazy to
research, download and install a proper newsreading program.

 

[CBFalconer]

When 01 -->> 0011.