[courses] [C] Finally get lesson 10 exc #2 (without understanding your bit-shift)
Laurel Fan
laurel at sdf.lonestar.org
Tue Nov 12 16:30:18 EST 2002
On Tue, Nov 12, 2002 at 06:11:19PM -0500, Morgon Kanter wrote:
> /* Count all 1s in the integer, please explain what I even did! */
> for(i = 0;i < BITS;i++) {
> if( ((x & (1 << i)) >> i)) count++;
Explanation:
(I'll use 8 bit integers for simplicity)
Looking at all those parens and operators at once can be pretty
overwhelming, so let's try this one step at a time:
Start from the inside of the parens:
1 << i
1 in binary looks like: 00000001
<< is shift left, which means you shift 1 i bits to the left.
So, for example:
1 << 0 = 00000001
1 << 1 = 00000010
1 << 2 = 00000100
1 << 3 = 00001000
1 << 4 = 00010000
... etc
If you look at this pattern, one thing you'll notice is that (1 << i)
in binary has a 1 in the i'th position from the right.
Next, we have:
x & (1 << i)
& is bitwise and. for example, if
x == 5
i == 2
1 << 2 == 00000100
x == 5 == 00000101
00000101 (5)
& 00000100 (1 << 2)
= 00000100 (1 << 2)
^ ^ ^--- 1 and 0 is 0
\ \---- 1 and 1 is 1
\----- 0 and 0 is 0
Now, what if:
x == 5
i == 1
1 << 1 == 00000010
00000101 (5)
& 00000010 (1 << 1)
= 00000000 (0)
So, if (x) in binary has a 1 in the same position as (1 << i), you get
(1 << i) back, but if (x) in binary has a 0 there, you get 0 back.
Try a few more examples if this doesn't make sense.
Combining this with what we learned about (1 << i), we can determine
that:
x & (1 << i)
is (1 << i) if x in binary has a 1 in the i'th position from the right
is 0 if x in binary has a 0 in the i'th position from the right
Is that enough to figure the rest out?
--
laurel at sdf.lonestar.org
http://dreadnought.gorgorg.org
More information about the Courses
mailing list