Bit fiddling

[saurabhnsit2001]

I have got few questions on bit fiddling!!
1. Fast way of Multiplying a No by 7.
2. Counting no of set bits in a 32 bit no without looping.
3. finding id a no is divisible by 3 or not without using %, /, and -
operators,

 

[W Marsh]

I have got few questions on bit fiddling!!

"I have got a few homework questions on bit fiddling"

 

[Richard Heathfield]

saurabhnsit2001 said:

I have got few questions on bit fiddling!!
1. Fast way of Multiplying a No by 7.

n *= 7;

I have no complaints about the computer's speed when it comes to multiplying
by 7 - it can do this way faster than I can.

2. Counting no of set bits in a 32 bit no without looping.

nbits = 0;
if(x & 0x1) ++nbits;
if(x & 0x2) ++nbits;
if(x & 0x4) ++nbits;
if(x & 0x8) ++nbits;
if(x & 0x10) ++nbits;
if(x & 0x20) ++nbits;
if(x & 0x40) ++nbits;
if(x & 0x80) ++nbits;
if(x & 0x100) ++nbits;
if(x & 0x200) ++nbits;
if(x & 0x400) ++nbits;
if(x & 0x800) ++nbits;
if(x & 0x1000) ++nbits;
if(x & 0x2000) ++nbits;
if(x & 0x4000) ++nbits;
if(x & 0x8000) ++nbits;
if(x & 0x10000) ++nbits;
if(x & 0x20000) ++nbits;
if(x & 0x40000) ++nbits;
if(x & 0x80000) ++nbits;
if(x & 0x100000) ++nbits;
if(x & 0x200000) ++nbits;
if(x & 0x400000) ++nbits;
if(x & 0x800000) ++nbits;
if(x & 0x1000000) ++nbits;
if(x & 0x2000000) ++nbits;
if(x & 0x4000000) ++nbits;
if(x & 0x8000000) ++nbits;
if(x & 0x10000000) ++nbits;
if(x & 0x20000000) ++nbits;
if(x & 0x40000000) ++nbits;
if(x & 0x80000000) ++nbits;

3. finding id a no is divisible by 3 or not without using %, /, and -
operators,

printf("Is %d divisible by 3?\n", n);
if((ch = getchar()) == 'y' || ch == 'Y')
{
printf("%d is divisible by 3.\n", n);
}

 

[Eric Sosman]

I have got few questions on bit fiddling!!

Wow! That is so exciting!! I can hardly contain
my enthusiasm!!!

1. Fast way of Multiplying a No by 7.

This is a trick question: There is no fast way to
multiply by seven. Multiplying by seven implies an
increase in magnitude, but magnitude decreases during
a fast.

2. Counting no of set bits in a 32 bit no without looping.

Another trick question: The double negative "no without"
implies that you *must* use a loop. If you submit a solution
that does not have a loop, you will receive a bad mark.

3. finding id a no is divisible by 3 or not without using %, /, and -
operators,

Your professor must be very fond of trick questions! In
this case you are asked about Freud's division of consciousness
into three parts (note "divisible by 3"): the ego, the id, and
the superego. This model is largely discredited by mainstream
psychiatrists, but is still taught as part of the history of the
discipline and still believed in by laypersons and a few fringe
operators.

How to find your id is a matter outside the C Standard.

 

[Thad Smith]

I have got few questions on bit fiddling!!
1. Fast way of Multiplying a No by 7.
2. Counting no of set bits in a 32 bit no without looping.

I like the number 3! You can use it to count bits!!

unsigned int nb(unsigned int n) {
return n>3? nb(n>>0x333/333)+nb(n<<3&033)(n+n+(3)/3)/3);
}

 

[Neil]

I have got few questions on bit fiddling!!
1. Fast way of Multiplying a No by 7.
2. Counting no of set bits in a 32 bit no without looping.
3. finding id a no is divisible by 3 or not without using %, /, and -
operators,

You mean bit "twiddling".

 

[jaks.maths]

I have got few questions on bit fiddling!!
1. Fast way of Multiplying a No by 7.
2. Counting no of set bits in a 32 bit no without looping.
3. finding id a no is divisible by 3 or not without using %, /, and -
operators,

Ans For Q3 is

#include<stdio.h>
main()
{
int n;
scanf("%d",&n);
while(n>=3)
{
n=n+(~3)+1;
}
if(n==0)
printf("\n it IS divisible by 3");
else
printf("Not divisible By 3");
}

 

[Andrew Poelstra]

Ans For Q3 is ...

Fixed version (mainly formatting):

#include <stdio.h>

int main(void)
{
int n;
scanf ("%d",&n);

while (n >= 3)
{
n += (~3);
n++;
}

if (n == 0)
printf ("\nThat number is divisible by 3\n");
else
printf ("\nThat number is not divisible By 3\n");

return 0;
}

Note that you declared main() wrong, you didn't put a \n at the end of
your printfs, you returned nothing from main, and you used either no
spacing, or tabs.

 

[Eric Sosman]

Andrew Poelstra wrote On 05/30/06 09:56,:

Fixed version (mainly formatting):

#include <stdio.h>

int main(void)
{
int n;
scanf ("%d",&n);

while (n >= 3)
{
n += (~3);
n++;
}

if (n == 0)
printf ("\nThat number is divisible by 3\n");
else
printf ("\nThat number is not divisible By 3\n");

return 0;
}

Why does it tell me that -42 is not divisible by 3?

 

[Andrew Poelstra]

Andrew Poelstra wrote On 05/30/06 09:56,:

Why does it tell me that -42 is not divisible by 3?

Because it is adding ~3, and in general bit twiddling is undefined
when working with negative integers. I should have caught that.

int n; should be unsigned int n;, or a better solution would have
been to set n to abs(n) right before the while loop.

 

[Keith Thompson]

Because it is adding ~3, and in general bit twiddling is undefined
when working with negative integers. I should have caught that.

int n; should be unsigned int n;, or a better solution would have
been to set n to abs(n) right before the while loop.

And if n == INT_MIN?

 

[Kevin Handy]

I have got few questions on bit fiddling!!

Please send us your teachers e-mail address so you
don't have to bother sending your homework to him,
since doing your own homework is too hard for you.

1. Fast way of Multiplying a No by 7.

Be 7 times badder. "no! no! No! No! No! NO! NO!"
(you get the exclimation points for free)

No = No * 7;

Table lookup.

2. Counting no of set bits in a 32 bit no without looping.

Wow! A 32 bit "no"! Did that hurt?
The "set bits" are the small pieces of scenery
on the stage, but you don't tell us what you did to
get a "no!" from it. It should still only a single
no, no matter how many times you bite it.

Table lookup.

3. finding id a no is divisible by 3 or not without using %, /, and -
operators,

What's an 'id-a-no'? Or is it you can't even copy
your homework properly?

All numbers are divisable by three. Try it yourself:
(1/3 = 0.333.., 2/3 = 0.666..., etc.)

You can use the '\' operater in mbasic, or the 'div'
operator in pascal.

Table lookup.

 

[Andrew Poelstra]

And if n == INT_MIN?

You would need to check for that, and then add three to ensure that you
don't overflow when you abs() it.

Any other special cases I should know about?

 

[Eric Sosman]

Andrew Poelstra wrote On 05/30/06 17:36,:

[...]

Why does it tell me that -42 is not divisible by 3?


Because it is adding ~3, and in general bit twiddling is undefined
when working with negative integers. I should have caught that.

int n; should be unsigned int n;, or a better solution would have
been to set n to abs(n) right before the while loop.

And if n == INT_MIN?

You would need to check for that, and then add three to ensure that you
don't overflow when you abs() it.

Any other special cases I should know about?

Only two that I can think of off-hand, both having
to do with issues of representation. Hint #1: Is the
absolute value of ~3 greater or less than a thousand?
Hint #2: Is the value of ~3 even or odd? (See section
6.2.6.2, paragraph 2).

The principal lesson is that it is usually silly to
use "bit fiddling" for tasks of the kind posed by the
O.P. (more likely, by the O.P.'s homework assignment).
As this thread demonstrates, such tasks can be trickier
than they might appear, and the "obvious" solutions have
pitfalls. Avoiding the pits can consume more execution
time than you save by avoiding the % or the * or whatever.

Let's try to imagine a scenario where speeding up a
divisibility-by-three test would make a useful improvement.
On the six-year-old machine sitting in front of me at the
moment, it takes about 0.172 seconds to test a million
numbers for divisibility by three using the % operator.
By resorting to bit fiddling I can cut the time to just
0.013 seconds, better than a thirteenfold speedup. Wow!

... but how much "Wow" is warranted? To save just one
second of the program's total execution time, I'd need to
use the faster method on about six and a half million
numbers. Six and a half million divisible-by-three tests,
and I save one, yes folks, a whopping ONE second. If it
took me, say, one minute to write the code and convince
myself I hadn't botched it, I'd break even after my program
had done three hundred eighty million divisibility tests --
until that moment, I'm running in the red.

How badly do you need three hundred eighty million
divisible-by-three tests?

Now, there can be circumstances where micro-optimization
of this sort is warranted. I maintain, though, that it is
NEVER warranted before convincing evidence has been found
that it is necessary.

 

[Walter Roberson]

Any other special cases I should know about?

I haven't been able to convince myself that it works
in one's complement.

 

[Andrew Poelstra]

[...]
Why does it tell me that -42 is not divisible by 3?
Because it is adding ~3, and in general bit twiddling is undefined
when working with negative integers. I should have caught that.
int n; should be unsigned int n;, or a better solution would have
been to set n to abs(n) right before the while loop.

Any other special cases I should know about?

I haven't been able to convince myself that it works
in one's complement.

Because I'm taking negative numbers, adding 3, and then taking
the absolute value, no bit twiddling is done until the number is
guaranteed to be positive.

 

[Andrew Poelstra]

Andrew Poelstra wrote On 05/30/06 17:36,:

[...]

Why does it tell me that -42 is not divisible by 3?


Because it is adding ~3, and in general bit twiddling is undefined
when working with negative integers. I should have caught that.

int n; should be unsigned int n;, or a better solution would have
been to set n to abs(n) right before the while loop.

And if n == INT_MIN?

You would need to check for that, and then add three to ensure that you
don't overflow when you abs() it.

Any other special cases I should know about?

Only two that I can think of off-hand, both having
to do with issues of representation. Hint #1: Is the
absolute value of ~3 greater or less than a thousand?
Hint #2: Is the value of ~3 even or odd? (See section
6.2.6.2, paragraph 2).

I don't have a Standard beside me right now; could you quote
6.2.6.2 for me?

I can't think of a reason for either hints to affect me. Here
is my current code (OP, I'd like some credit for your course):

#include <stdio.h>
#include <math.h>

int main(void)
{
signed int n; /* Best to be explicit about signedness */
unsigned int o; /* in this code. */

printf ("Enter a number: ");
scanf ("%d", &n);

if (n < 0)
{
n += 3; /* Ensure that n isn't INT_MIN */
o = abs(n);
} else {
o = n;
}

/* From now on, o is our variable, and is unsigned. */
/* Note that 0 <= o <= INT_MAX */

while (o >= 3)
o += (unsigned int) (~3) + 1; /* Is this cast necessary? */

if (o == 0)
printf ("\nThat number is divisible by 3\n");
else
printf ("\nThat number is not divisible By 3\n");

return 0;
}


For now I'm going to flip through my Discrete Mathematics
textbook and see if I can come up with a cleverer algorithm
for determining 3-divisibility in base 2.

The principal lesson is that it is usually silly to
use "bit fiddling" for tasks of the kind posed by the
O.P. (more likely, by the O.P.'s homework assignment).
As this thread demonstrates, such tasks can be trickier
than they might appear, and the "obvious" solutions have
pitfalls. Avoiding the pits can consume more execution
time than you save by avoiding the % or the * or whatever.

Let's try to imagine a scenario where speeding up a
divisibility-by-three test would make a useful improvement.
On the six-year-old machine sitting in front of me at the
moment, it takes about 0.172 seconds to test a million
numbers for divisibility by three using the % operator.
By resorting to bit fiddling I can cut the time to just
0.013 seconds, better than a thirteenfold speedup. Wow!

Let's consider that right now I'm running slrn on a 12-year-old
machine, and every so often I boot up a computer that is now about
15 years old to work on. Micro-optimization makes a big difference
on those computers.

 

[jaks.maths]

I have got few questions on bit fiddling!!
1. Fast way of Multiplying a No by 7.
2. Counting no of set bits in a 32 bit no without looping.
3. finding id a no is divisible by 3 or not without using %, /, and -
operators,

Ans for Q1 is

n*7= n*(8-1)=n*8-n=n<<3-n

Ans for Q2 is

#include<stdio.h>
int main()
{
int n,c;
scanf("%d",&n);
c=0;
while(n!=0)
{
n&=n-1;
c++;
}
printf("\n No of One's in %d=%d",n,c);
}

 

[Guest]

Ans for Q1 is

n*7= n*(8-1)=n*8-n=n<<3-n

What if n*8 overflows, but n*7 doesn't?

Ans for Q2 is
[...]
while(n!=0)

I don't think "without looping" is a typo for "with looping".

 

[Ralf Schallenberg]

Ans for Q1 is
n*7= n*(8-1)=n*8-n=n<<3-n

n<<3-n
is equivalent to
n<<(3-n)