Bit fiddling

[Eric Sosman]

Andrew Poelstra wrote On 05/31/06 00:46,:

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? */

It's not necessary, but it's also not sufficient.
The value of `(unsigned int) (~3) + 1' depends on the
way the implementation represents signed integers:

- Two's complement: ~3 is equal to -4, the cast
converts it to UINT_MAX+1-4 == UINT_MAX-3, and
adding 1 gives UINT_MAX-2.

- Ones' complement: ~3 is equal to -3, the cast
converts it to UINT_MAX+1-3 == UINT_MAX-2, and
adding 1 gives UINT_MAX-1.

- Signed magnitude: ~3 is equal to -(INT_MAX-3),
the cast converts it to UINT_MAX+1+INT_MAX-3
== INT_MAX-3 (probably), and adding 1 gives
INT_MAX-2.

You should have written `~(unsigned int)3 + 1',
or simply `~3u + 1' (or even `~3u + 1u').

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.




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.

On the machine mentioned above, mod-and-zero-test took
0.172 seconds to test the numbers 0..999999 for divisibility
by three. Division by repeated subtraction took 474 seconds
to do the same thing. Slowing something down by more than
two hundred seventy-five thousand percent is certainly "a big
difference," but few people would call it an "optimization."

 

[Dave Thompson]

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

I'm not going to bother posting all of it with my delay, but I have a
useful if embarassing mnemonic: 6.2.6 is about representation (and .2
about integers) because it immediately follows 6.2.5 types which used
to be 6.1.2.5, so treated as a pseudo obsolete stock quotation it
incremented from 6 1/8 to 6 1/4 . Yes, I do need to get a life.

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):

That section (now explicitly) allows ones' complement and sign and
magnitude but your bitwise-complement plus one trick only works in
two's complement.

#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);

Should check for scan error, or at least have initialized the auto n
to a non-indeterminate value in case of that.

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? */

It's not even sufficient. In 1sC ~3 is -3, which becomes UINT_MAX+1
-3; +1 gives UINT_MAX+1 -2, which has the effect in unsigned=modular
arithmetic of subtracting two. Without the cast ~3 + 1 becomes -2,
which is converted to unsigned and effectively subtracts 2. In S&M ~3
is a huge negative number (-INT_MAX+3), and I'm pretty sure there's no
case where it works regardless of how unsigned uses the sign bit
and/or any padding bits.

You need to have unsigned _before_ complementing:
~(unsigned)3 + 1 or just ~3U + 1

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.

Even on those computers subtraction does tend to be available.
(Although on PDP-8, and I assume -5, it is generally 1 insn more than
addition -- which is indeed 2sC.) But iterated subtraction or addition
is unlikely to be an optimization for any but quite small values --
which could probably as well or better be optimized as a lookup table
on even machines that are 30 to 40 years old. (If you can afford the
power and airconditioning to run one. Or more likely emulate it.)

- David.Thompson1 at worldnet.att.net