Thread: A Standard CS introductory problem

Hello, everyone.

I'm not a CS major, but I just nosing around CS department pages and occasionally try to solve the problems that are posted.

I guess some of you are familiar with the "twiddling bits" problem.

Like creating an AND function with just ~ and |.

Well, I'm stumped on this one.

Code:

/* 
 * evenBits - return word with all even-numbered bits set to 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 8
 *   Rating: 2
 */
int evenBits(void) {
    return 2;
}

My compiler has 32bit integers, so even allowing that max ops is 16 and not 8, I can't seem to solve it without using some 32 operands.

The site said I'm not supposed to use loops but just to make the code shorter, here's what I did.

Code:

int evenBits(void) {
	int i, j;
	i = 0;
	for(j = 31; j > 0; j -= 2)
		i |= (1 << j);
    return i;
}

Counting the times I use | and <<, it's about 32 times, I guess.
Is there a way to do this with just 16 (or 8)?

evenBits - return word with all even-numbered bits set to 1

Huh?

>> Huh?

10101010101010101010101010101010

It means word as in natural size of data on the machine (in this case 32 bits).

Try thinking about how to combine the current state of the bits with a modified version of the current state of the bits to set multiple bits at the same time. For example, if you had 0000000010101010, how would you get it to be 1010101010101010 in one line of code (but potentially multiple operations).

Ah, here's the secret:

The bitwise operators operate on ALL of the bits at once.

So, if you perform a bitwise OR between the unknown and 55555555 hex (1,431,655,765 decimal), you will set all of the even bits to one.

55555555 hex = 0101 0101 0101 0101... binary.

That's the other secret... Always use hex when manipulating bits. Its easier (for humans) to convert between hex and binary, than between decimal and binary.

Note - It is conventional to start counting bits with the LSB (least significant bit) as "bit-0". Using that convention, bit-0 is even, and the MSB (bit-31) is odd.

I understood Daved's hint. And I got the following code.

Code:

int evenBits(void) {
	int i;
	i = 1 << 1;
    i |= i << 2;
    i |= i << 4;
    i |= i << 8;
    i |= i << 16;
    return i;
}

That would suffice, right? So I managed to do it with 9 of the designated operands.

But I'm afraid I'm not getting what dougdbug is saying. I understand that
55555555 hex = 0101 0101 0101 0101... binary
but doesn't that defeat the purpose of trying to set the bits that way through a set of operations?
Or is there something that I'm missing here?

I think DougDbug was assuming that the function should take in some unknown number and convert it to be all even bits on. I understood the task to mean start from scratch and use bit manipulation to do the task. If you use his interpretation it wouldn't make as much sense, since you could do it in only 2 operations.

My quick solution was similar to yours, also using 9 operands. If DougDbug was right about the first bit being bit-0 (i.e. 01010101010101010101010101010101), then you can make your code use only 8 operands, so that just might be the answer.