Help with bitwise operators

[llamanaru]

This is in fact homework, thank you for any help you can give me.

So the assignment is to implement a series of functions using only bitwise/logical operators, no while loops, no if statements, etc. in C in a certain number of operators.
The exact rules are spoilered:

Spoiler:

Each "Expr" is an expression using ONLY the following:
1. Integer constants 0 through 255 (0xFF), inclusive. You are
not allowed to use big constants such as 0xffffffff.
2. Function arguments and local variables (no global variables).
3. Unary integer operations ! ~
4. Binary integer operations & ^ | + << >>

Some of the problems restrict the set of allowed operators even further.
Each "Expr" may consist of multiple operators. You are not restricted to
one operator per line.

You are expressly forbidden to:
1. Use any control constructs such as if, do, while, for, switch, etc.
2. Define or use any macros.
3. Define any additional functions in this file.
4. Call any functions.
5. Use any other operations, such as &&, ||, -, or ?:
6. Use any form of casting.

You may assume that your machine:
1. Uses 2s complement, 32-bit representations of integers.
2. Performs right shifts arithmetically.
3. Has unpredictable behavior when shifting an integer by more
than the word size.

I'm having trouble with two of the functions, logicalNeg and bitCount. The first is to implement the ! operator without actually using !. Bit count is to count the number of set bits. Exact rules again spoilered.

logicalNeg:

Spoiler:

logicalNeg - implement the ! operator, using any of the legal operators except !
Examples: logicalNeg(3) = 0, logicalNeg(0) = 1
Legal ops: ~ & ^ | + << >>
Max ops: 12
Rating: 4

bitCount

Spoiler:

bitCount - returns count of number of 1's in word
Examples: bitCount(5) = 2, bitCount(7) = 3
Legal ops: ! ~ & ^ | + << >>
Max ops: 40
Rating: 4

Ratings are out of 4 by the way.

My attempts are spoilered below.

logicalNeg:

Spoiler:

Code: Select all

int logicalNeg(int x) {
   int i = (~x+1) >> 31;
   int j = (x+1) >> 31;
   i = i|j;
   i = i&1;
   return i^1;
}

bitCount:

Spoiler:

Code: Select all

int count = 0;
   count += x&0x01;
   x = x>>1;
   count += x&0x01;
   x = x>>1;
   count += x&0x01;
   x = x>>1;
   count += x&0x01;
   x = x>>1;
   count += x&0x01;
   x = x>>1;
   count += x&0x01;
   x = x>>1;
   count += x&0x01;
   x = x>>1;
   count += x&0x01;
   x = x>>1;
   count += x&0x01;
   x = x>>1;
   count += x&0x01;
   x = x>>1;
   count += x&0x01;
   x = x>>1;
   count += x&0x01;
   x = x>>1;
   count += x&0x01;
   x = x>>1;
   count += x&0x01;
   x = x>>1;
   count += x&0x01;
   x = x>>1;
   count += x&0x01;
   x = x>>1;
   count += x&0x01;
   x = x>>1;
   count += x&0x01;
   x = x>>1;
   count += x&0x01;
   x = x>>1;
   count += x&0x01;
   x = x>>1;
   count += x&0x01;
   x = x>>1;
   count += x&0x01;
   x = x>>1;
   count += x&0x01;
   x = x>>1;
   count += x&0x01;
   x = x>>1;
   count += x&0x01;
   x = x>>1;
   count += x&0x01;
   x = x>>1;
   count += x&0x01;
   x = x>>1;
   count += x&0x01;
   x = x>>1;
   count += x&0x01;
   x = x>>1;
   count += x&0x01;
   x = x>>1;
   count += x&0x01;
   x = x>>1;
   count += x&0x01;
   x = x>>1;
   return count;

logicalNeg works for every case but -1, because for zero and -1 the first two statements give an equivalent OR statement.

bitCount works fine, but it's more than twice the allowed operators, I've been trying to figure out a way to condense what I have, but I haven't had any luck. It's the while loop method extended.

Thanks again for any help,
--Joe

[quintopia]

Here's a quick idea for the not: try ORing all the bits together, then doing a bitwise not on the result.

Yes, I realize the naive way of ORing all the bits together requires more operations than you're allowed, but if you're clever with your shifting, I'm sure you can see a way to drastically cut the number of ORs required

Err, never mind, I think this is still too many ops

This should work: bitwise not, and all bits together with clever shifting

[phlip]

quint has the right idea... you want to build a number which has a bit that's the logical or of all the bits in your original number. Obviously, to do this the naive way would use too many operations, but remember that your bitwise or is able to do many logical ors all at once.

If that's too obscure, here's a more direct hint:

Spoiler:

When you come in, you have a number that's True iff there's a 1 anywhere in the 32 bits. How many operations would it take you to build a number such that the original number should be treated as True iff this new number has a 1 in the last, say, 16 bits?

As for bit-count... the traditional trick for doing this one without any branches requires large constants to use as bitmasks, which you're not allowed... I think you have enough operands allowed to build them up from individual bytes, though...

[edit] Just to confirm it is possible... I have a working logicalNot using 12 operations, and bitCount using 36.

[ATCG]

I very much like the direction you've taken with your logicalNeg function. (I would like to think that I would have come up with it myself, but I suspect I wouldn't have.) Your fundamental approach to detecting x == 0 is sound; it's just the execution that doesn't quite come together. Consider replacing the first two declarations in your proposed solution with the following:

Code: Select all

   int i = ~x;
   int j = i + 1;


Think of i as "before incrementation" and j as "after" and work through what the sign bits of i and j look like for different values of x. The remaining logic should quickly suggest itself.

For bitCount, here's a fragment of code that might suggest an alternative attack to the problem:

Code: Select all

   \\  My not-quite-C code
   int mask = 0x11;                \\  Beat the restriction
   mask = (mask <<  8) | mask;     \\    on
   mask = (mask << 16) | mask;     \\    big constants.
   \\  mask == 0x11111111
   int acc = x & mask;
   acc = acc + ((x >> 1) & mask);
   acc = acc + ((x >> 2) & mask);
   acc = acc + ((x >> 3) & mask);


What does acc contain after this bit of code finishes?

Keep us posted on your progress.

EDIT: ninja'd by phlip. Think of my code as illustrating his points concerning bitCount.

[phlip]

Oh, so that's what he's trying to do with logicalNot... very clever. Using that trick, I've got it down to 6 operators...

[jareds]

Oops, I was ninja'd by everybody about bit count. I was going to post a hint for bit count, but instead I'll just say it's possible with 27 operators.

[mr-mitch]

Assuming brackets don't count as operators, it's possible to do bitcount using 22 bitwise operators. It's very similar to the way you wrote your previous code.

[llamanaru]

quintopia, your second method worked perfectly, thanks for the help. Got it in 12 ops.
ATCG, the problem wasn't with 0, it was with -1. For both these values the OR statement would be equivilant, just with i and j reversed. Your code probably fixes this error too though, and it seems interesting so I'll see if I can work it out along with the bitcount.

mr-mitch, brackets suggest arrays, functions, or control statements, none of which are allowed for the assignment. Am I wrong about what you're thinking?

Thanks again for all your help, I'll keep you posted.

EDIT: Also, sorry for the wrong forum.

[quintopia]

Oh, so that's what he's trying to do with logicalNot... very clever. Using that trick, I've got it down to 6 operators...

The best I can do with as few operators is the opposite of not. (aka, is a bit set?) If I stare at it for a bit, I bet it comes to me.

[mr-mitch]

mr-mitch, brackets suggest arrays, functions, or control statements, none of which are allowed for the assignment. Am I wrong about what you're thinking?

I was referring to using brackets for precendence.

eg x >> 1 + 1 is different to (x>>1) + 1 in most compilers (if not all).

Code: Select all

#include <stdio.h>

int main()
{   
   int x = 10;
   printf("x = 10;\nx >> 1 + 1 == %i\n(x>>1)+1 == %i\n", x >> 1 + 1, (x >> 1) + 1);
   return 0;
}   


x = 10;
x >> 1 + 1 == 2
(x>>1)+1 == 6

Is this allowed? If so, you can do it in the number of operators I said before, if not, I suppose it's back to the drawing board for me.

[Rysto]

eg x >> 1 + 1 is different to (x>>1) + 1 in most compilers (if not all).

Order of operations is set by the standard, so it had better be the same for all compilers.

[hotaru]

Assuming brackets don't count as operators, it's possible to do bitcount using 22 bitwise operators. It's very similar to the way you wrote your previous code.

it's actually possible with 21 operators.

[llamanaru]

mr-mitch: Oh, those brackets... Yeah, you can according to the rules of the assignment use those brackets as much as you'd like.

[bigRed]

Hi I am new to the forums and have been lurking for awhile but finally found the need to participate. BTW my favorite comic was when the man tells his wife to make him a sandwich and she says no and then he says sudo make me a sandwich and she says ok hahahaha.

Ok I know this topic has been dead for awhile but I am doing something very similar to bitCount, actually it’s the same thing with the same restrictions. So far I can count the bits but I use about 50+ operations and I can only use 40ish.

So here is the psudo code:

Code: Select all

Int x = numberToCount;
Int mask = 0x01;
Int count = 0;

Count += x & mask;
Count += (x >> 1) & mask;
Count += (x >> 2) & mask;
.
.
.


So I read the hint about making the mask be 0xFF, mask << 24 then mask >> 24 to make it 0x111111111111111… and then do basically the same thing. I don’t know how this saves any instructions and I have been working on this for awhile but cant find the clue to keep me going forward. Any suggestions????

[Yakk]

They didn't make mask equal to 0xFFFFFFFF.

[You, sir, name?]

Idea for !-operation:

Code: Select all

int negtest(unsigned int i) { // The *unsigned* int type is important here
  // ~0 = 0xffffffff = -1
  // MSB of (i + ~0) ^ i flips on i=0 and i=-2147483648 (INT_MIN)
  // &'ed with ~i to remove the 0x8000 case
  // shifting by 31 to get 0 or 1
  return (((i + ~0) ^ i) & ~i) >> 31;
}


I count 6 operations.

[cemper93]

Negation, 5 ops:

Code: Select all

int invert(int i) {
  mask = 255 | (255 << 8);
  mask |= mask << 16;
  return mask ^ i;
}

That's because XOR of a bit with 1 is always the bit inverted (1 ^ 1 = 0; 0 ^ 1 = 1). This only works if "logical negation" is to be understood in the C sense (0 = false, everything else = true).

[You, sir, name?]

Negation, 5 ops:

Code: Select all

int invert(int i) {
  mask = 255 | (255 << 8);
  mask |= mask << 16;
  return mask ^ i;
}

That's because XOR of a bit with 1 is always the bit inverted (1 ^ 1 = 0; 0 ^ 1 = 1). This only works if "logical negation" is to be understood in the C sense (0 = false, everything else = true).

That inverts all the bits.

So
invert(-1) = 0x00000000
invert(0) = 0xffffffff
invert(1) = 0xfffffffe

While
!(-1) = 0
!0 = 1
!1 = 0

As the task is to "implement the ! operator", I don't think that qualifies.

Btw, your code can also be simplified to

Code: Select all

int invert(int i) {
  return i ^ ~ 0;
}

[Goplat]

return (((i + ~0) ^ i) & ~i) >> 31;

The ^ is unnecessary; you can just do ((i + ~0) & ~i) >> 31.

Edit: if right shift always has to be signed, then this will work: (((~i + 1) | i) >> 31) + 1

[Yakk]

What number, when negated, is non-negative, and it non-negative itself?
((-i)|(i))>>31
-i is (~i+1)
((~i+1)|i)>>31
which is 1 iff i is non-zero.

Now, we don't want that value, but the opposite:
(~((~i+1)|i))>>31
which is 5 ops.

Now, we could expand the ~:
(~(~i+1)&~i)>>31
which is also 5 ops (and one temporary variable so we don't double-compute ~i).

You'll note that ~(~i+1) is similar to (i-1) above. -x = (~x+1), so ~(~i+1) = ~(-i). -x-1 = ~x, so ~(-i) = -(-i)-1 = i-1.

This shows how ~(~i+1) = (i+~0) = i-1.

[You, sir, name?]

return (((i + ~0) ^ i) & ~i) >> 31;

The ^ is unnecessary; you can just do ((i + ~0) & ~i) >> 31.

It started out as an algorithm that also fired at INT_MIN and the &~i was a patch for that.