The Shed is going Social! Join us on FaceBook and Twitter and chime in on the conversation.
|
 |
|
Dev Shed Forums
> Programming Languages
> C Programming
|
Bit puzzle help
Discuss Bit puzzle help in the C Programming forum on Dev Shed. Bit puzzle help C programming forum discussing all C derivatives, including C#, C++, Object-C, and even plain old vanilla C. These languages are low level languages, and used on projects such as device drivers, compilers, and even whole computer operating systems.
|
|
 |
|
|
|
|

Dev Shed Forums Sponsor:
|
|
|

October 2nd, 2012, 10:01 PM
|
|
Registered User
|
|
Join Date: Oct 2012
Posts: 1
Time spent in forums: 28 m 29 sec
Reputation Power: 0
|
|
|
Bit puzzle help
Can you explain how the following two "bit puzzles" achieve what the title of the problems say they do.
1. Absolute Value
int abs(int x){
int sign = x >> 31;
int neg_x = ~x+1; //two's compliment
return (neg_x & sign) | (x & ~sign);
}
2. Lazy Addition
// assumes a + b + c + d <= 127
// and that a,b,c,d are all positive
// returns a + b + c + d using only 2 additions
int add4(int a, int b, int c, int d){
x = a << 8 | b;
y = c << 8 | d;
int q = x + y;
return (q & 0xff) + (q >> 8);
}
All the explanation in the world would be extremely helpful and appreciated!! Thank you!
|

October 3rd, 2012, 12:16 AM
|
 |
Contributed User
|
|
|
|
There are more here, with explanations.
Perhaps it will help you figure it out.
bit hacks
|

October 3rd, 2012, 12:32 AM
|
 |
Banned ;)
|
|
Join Date: Nov 2001
Location: Woodland Hills, Los Angeles County, California, USA
|
|
|
Cute stuff. HINTS:
1. Print out the results of (neg_x & sign) and (x & ~sign) separately. Then convert them into binary and you'll get an idea of what the | does (it is pretty easy once you see the two results in binary to figure out what is going on)
2. The reason why this works is because initially the numbers all occupy one byte of (an assumed 32 bit) int. i.e. the numbers are of the format 000a, 000b, 000c, 000d. By bit shifting the bits, it essentially makes two variables
X = 00ab
Y = 00cd
where each variable occupies one byte of the int (this is why there is a restriction that a, b, c and d are <= 127) Again, printing x, y in binary along with a and n will tell you exactly what is happening
Now it adds the numbers, which will add the numbers on individual bytes like this:
Q = 00(a+c)(b+d)
Again, if you print Q in binary, you'll see what is going on. Also note here the restriction that 0 <= a, b, c, d <= 127. Because if the result of (b+d) is > 255, then it will overflow into the calculation of (a+c). Overflows cannot happen if both numbers are <= 127.
The final step is to separate byte (b+d) and byte (a+c) and then add them together to get the final result.
__________________
Up the Irons
What Would Jimi Do? Smash amps. Burn guitar. Take the groupies home.
"Death Before Dishonour, my Friends!!" - Bruce D ickinson, Iron Maiden Aug 20, 2005 @ OzzFest
Down with Sharon Osbourne
|
Developer Shed Advertisers and Affiliates
| Thread Tools |
Search this Thread |
|
|
|
| Display Modes |
Rate This Thread |
Linear Mode
|
|
Posting Rules
|
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
HTML code is Off
|
|
|
|
|