c bitwise operation to match description

Question

I'm supposed to match the worded descriptions to the bitwise operations. W is one less than the total bits in a's and b's data structure. So if a is 32 bits long W is 31 Here are the worded descriptions:

1. One’s complement of a
2. a.
3. a&b.
4. a * 7.
5. a / 4 .
6. (a<0)?1:-1.

and here are the bitwise descriptions:

a.  ̃( ̃a | (b ˆ (MIN_INT + MAX_INT)))
b. ((aˆb)& ̃b)|( ̃(aˆb)&b)
c. 1+(a<<3)+ ̃a
d. (a<<4)+(a<<2)+(a<<1)
e. ((a<0)?(a+3):a)>>2
f. a ˆ (MIN_INT + MAX_INT)
g.  ̃((a|( ̃a+1))>>W)&1
h.  ̃((a >> W) << 1)
i. a >> 2

I have a few of them solved namely:

a.  ̃( ̃a | (b ˆ (MIN_INT + MAX_INT))) = a & b
b. ((aˆb)& ̃b)|( ̃(aˆb)&b) = a
c. 1+(a<<3)+ ̃a = 7 * a
d. (a<<4)+(a<<2)+(a<<1) = 16*a + 4*a + 2*a = 22*a
e. e. ((a<0)?(a+3):a)>>2 = (a<0)?(a/4 + 3/4) : a/4 = a/4 + ((a<0)?(3/4:0)
f. a ˆ (MIN_INT + MAX_INT) = ~a
i. a >> 2 = a/4

So basically all I need help with are g and h

g.  ̃((a|( ̃a+1))>>W)&1
h.  ̃((a >> W) << 1)

If you wouldn't mind could you also provide an explanation if you could?

I think this is what is going on with g:

g.  ̃((a|( ̃a+1))>>W)&1 = ~((a|(two's complement of a) >>W)&1 
= ~((a|sign of two's complement of a) &1 = ~(-a)&1

but this could be 1 or 0 so I don't think I did this right.

and for this one:

h.  ̃((a >> W) << 1) = ~((sign of a) << 1) = ~((sign of a)*2) 

and I don't know where to go from there...

Thank you for your help!!!

Answer 1

For g, consider that (a|~a) sets all bits to 1, so:

~((a|~a) >> W) & 1
~(all_ones >> W) & 1
~1 & 1
0

The only way adding 1 to ~a could possibly affect this result is if the addition flipped the most significant bit of ~a (due to the right shift by W). That can only happen if a is 0 or 2^W. In the latter case, we will get the same result as above because the top bit of (a|X) will always be set. However, when a is 0 ~a+1 (0's twos complement) is also 0 and the final result of the entire expression will instead be 1.

Therefore, g is 1 when a is zero, otherwise it is 0 (i.e. - g is equivalent to the C expression a == 0). That seemingly doesn't match any of your worded descriptions. Indeed, I don't see how any expression (X & 1) possibly matches any of your worded descriptions. None of your worded descriptions matches an expression that evaluates to only 0 or 1 (for all values of a, b).

For h, consider that if a is negative, then its top most bit is set. Because a is signed, right shifting it 31 positions drags the sign bit across all 32 bits of a. Then left shifting it one position sets the least significant bit to 0. Complementing that yields 1. If a is non-negative, then its top most bit is 0 and right shifting that 31 positions yields 0. Left shifting that 1 position still yields 0. Complementing that yields all bits set, which is the 2's complement rep of -1. Therefore, h is equivalent to (a < 0 ? 1 : -1) or #6 of your worded descriptions.