awood said:
Well, I came across this comment, and I was wondering if I could get some C/C++ expertise to explain it a bit more:
Quote
I think you meant "if(j % 30 == 0)" or better yet "if((j & 0xFFFF) == 0xFFFF)" in your main loop. Use the latter (that is, "if((j & 0xFFFF) == 0xFFFF)") for a huge speed increase.
These two are
not equivalent. The first (j % 30 == 0) checks whether j is divisible by 30. What the % operator does is divide the left operand (j) by the right operand (30) and returns the remainder. When the remainder is 0, that means left was divisible by right.
What the second does is checks whether the lower 16 bits of j are all set. Each hex digit represents 4 bits:
hex dec binary
0 0 0000
1 1 0001
2 2 0010
3 3 0011
4 4 0100
5 5 0101
6 6 0110
7 7 0111
8 8 1000
9 9 1001
A 10 1010
B 11 1011
C 12 1100
D 13 1101
E 14 1110
F 15 1111
So, hex FFFF is binary 1111 1111 1111 1111. This is decimal 65535, or if j is a signed short, -1. (Any
signed,
integral variable that has
all its bits set is -1 on two's complement machines [which you are using]).
Quote
I do not understand the use of bitwise AND, as well as the 0xFFFF. The appropriate use of hex has never showed up on my radar, and I would like to know more about it. If anyone has any online resources they could point me to that cover this, that would be great.
Let's take things down to four bits at a time to save me some typing:
I'll assume that j = 13 --> hex 0xD --> binary 1101
Binary AND checks whether the bits are set in both left and right operands, so:
j & 13 == 13 --> 1101 AND 1101 = 1101 (because all bits in j are also set in 13)
j & 15 == 13--> 1101 AND 1111 = 1101 (as above)
j & 10 == 8 --> 1101 AND 1010 = 1000 (because only the first bit is set in both)
j & 9 == 9 --> 1101 AND 1001 = 1001
So far so good.
If you look at my table above, you might notice that all powers of 2 (1, 2, 4 and 8) have only 1 bit set and all bits to the right of that are always 0. This means that any multiple of those number will also have those rightmost bits 0. Think about multiplying any number by one thousand. Any number that is a multiple of one thousand will end in at least 3 zeroes. The same goes in binary. That means that any multiple of 8 (binary 1000) will also end in 3 zero bits. Anything else is the remainder of a division. To check those last 3 bits, you will need to AND them with a number that has all those bits set which is always one lower than this power of 2, (decimal 7, binary 0111).
So: (x & 7) will get the lowest 3 bits of x. If they are all set, the result will of course be 7.
15 & 7 == 7 --> 1111 AND 0111 = 0111 (remainder == 7, so 15 is not divisible by 8)
8 & 7 == 0 --> 1000 AND 0111 = 0000 (remainder == 0, so 8 is divisible by 8 DuH!)
59 & 31 == 27 --> 0011 1011 AND 0001 1111 = 0001 1011 (59 is not divisible by 32)
128 & 7 == 0 --> 1000 000 AND 0000 0111 = 0000 0000 (128 is divisible by 8)
Since computers tend to be faster at bitwise logics than at multiplication and division, there used to be a time when it was a feasible optimisation to replace operations %32 by the functionally equivalent &31. Modern optimising compilers should do this automatically though. Even if they don't, it's very rarely necessary unless this is in some critical inner loop. A Pentium 4 can do many millions of integer divisions per second anyway.
There's a rather good article on GameDev about the whole decimal/hexadecimal/binary thing:
click here
0
