CODEWITHSUNDEEP
cbit-manipulation
user3769402
user3769402

Reputation: 211

Having trouble trying to solve bit level manipulation puzzle in C

So I have to use bitwise manipulation to solve this problem.

Should duplicate effect of C expression (x*63),
including overflow behavior.
Examples: multi63(1) = 63
   multi63(-1) = -63
Available ops: ! ~ & ^ | + << >>

Maybe I'm not understanding what is being looked for but Im trying different variations and each time my result is either really close to what needs to be returned but isn't correct.

This is what I was currently playing with. I figured if I could mask x, which is the 1 perimeter, then I would know whether I'm multiplying by negative or positive. 

int y = x>>31;

return ~(y^x)

This returns:

 Test times63(2147483647[0x7fffffff]) failed...
...Gives -2147483648[0x80000000]. Should be 2147483585[0x7fffffc1]

And If I try to return 2147483585[0x7fffffc1] it tells me I need to return -2147483648[0x80000000] so I'm confused as to what I need to return.

Upvotes: 0

Views: 178

Answers (1)

Beko
Beko

Reputation: 1002

As a general(!) rule you can consider these formulas for an expression x*N, using shifts and addition/subtraction only:

A: (x << n) + (x << n-1) << + ... + << (x << m)

B: (x << n+1) - (x << m)

N can be viewed as a sequence of 0's and 1's [(0...0)(1...1)(0...0)(1...1)]. You have to consider runs of 1's from bit position n down to bit position m, where n == m is possible.

In your case N = 63, which is 011_1111 in binary. So we have n = 5 and m = 0. As a simple example assume x = 2:

Using B: (2 << 6) - (2 << 0) == (2*64) - (2*1) == 128 - 2 == 126 (You can try out A for yourself, it works as fine.)

Just to demonstrate the process on another number, assume that N = 55 and x = 2. 55 in binary: 011_0111. This time we have two sequences of 1's. n1 = 5, m1 = 4 and n2 = 2 and m2 = 0.

Using B for n1/m1: (2 << 6) - (2 << 4) == (2*64) - (2*16) == 128 - 32 == 96

Using B for n2/m2: (2 << 3) - (2 << 0) == (2*8) - (2*1) == 16 - 2 == 14

Adding both results together yields 110, the desired value.

Upvotes: 1

Related Questions