What does >> and 0xfffffff8 mean?_问答_开发者_运维开发者技术经验分享

I was told that (i >> 3) is faster than (i开发者_Go百科/8) but I can't find any information on what >> is. Can anyone point me to a link that explains it?

The same person told me "int k = i/8, followed by k*8 is better accomplished by (i&0xfffffff8);" but again Google didn't help m...

Thanks for any links!

As explained here the >> operator is simply a bitwise shift of the bits of i. So shifting i 1 bit to the right results in an integer-division by 2 and shifting by 3 bits results in a division by 2^3=8.

But nowadays this optimization for division by a power of two should not really be done anymore, as compilers should be smart enough to do this themselves.

Similarly a bitwise AND with 0xFFFFFFF8 (1...1000, last 3 bits 0) is equal to rounding down i to the nearest multiple of 8 (like (i/8)*8 does), as it will zero the last 3 bits of i.

Bitwise shift right. i >> 3 moves the i integer 3 places to the right [binary-way] - aka, divide by 2^3.

int x = i / 8 * 8:

1) i / 8, can be replaced with i >> 3 - bitwise shift to the right on to 3 digits (8 = 2^3)

2) i & xfffffff8 comparison with mask For example you have:

i = 11111111
k (i/8) would be: 00011111  
x (k * 8) would be: 11111000

Therefore the operation just resets last 3 bits: And comparable time cost multiplication and division operation can be rewritten simple with

i & xfffffff8 - comparison with (... 11111000 mask)

They are Bitwise Operations

The >> operator is the bit shift operator. It takes the bit represented by the value and shifts them over a set number of slots to the right.

Regarding the first half:

>> is a bit-wise shift to the right.

So shifting a numeric value 3 bits to the right is the same as dividing by 8 and inting the result.

Here's a good reference for operators and their precedence: http://web.cs.mun.ca/~michael/c/op.html

The second part of your question involves the & operator, which is a bit-wise AND. The example is ANDing i and a number that leaves all bits set except for the 3 least significant ones. That is essentially the same thing happening when you have a number, divide it by 8, store the result as an integer, then multiply that result by 8.

The reason this is so is that dividing by 8 and storing as an integer is the same as bit-shifting to the right 3 places, and multiplying by 8 and storing the result in an int is the same as bit-shifting to the left 3 places.

So, if you're multiplying or dividing by a power of 2, such as 8, and you're going to accept the truncating of bits that happens when you store that result in an int, bit-shifting is faster, operationally. This is because the processor can skip the multiply/divide algorithm and just go straight to shifting bits, which involves few steps.

Bitwise shifting.

Suppose I have an 8 -bit integer, in binary

01000000

If I left shift (>> operator) 1 the result is

00100000

If I then right shift (<< operator) 1, I clearly get back to wear I started

01000000

It turns out that because the first binary integer is equivelant to

0*2^7 + 1*2^6 + 0*2^5 + 0*2^4 + 0*2^3 + 1*2^2 + 0*2^1 + 0*2^0

or simply 2^6 or 64

When we right shift 1 we get the following

0*2^7 + 0*2^6 + 1*2^5 + 0*2^4 + 0*2^3 + 1*2^2 + 0*2^1 + 0*2^0

or simply 2^5 or 32

Which means

i >> 1

is the same as

i / 2

If we shift once more (i >> 2), we effectively divide by 2 once again and get

i / 2 / 2

Which is really

i / 4

Not quite a mathematical proof, but you can see the following holds true

i >> n == i / (2^n)

That's called bit shifting, it's an operation on bits, for example, if you have a number on a binary base, let's say 8, it will be 1000, so

x = 1000;
y = x >> 1; //y = 100 = 4
z = x >> 3; //z = 1

Your shifting the bits in binary so for example:

1000 == 8

0100 == 4 (>> 1)

0010 == 2 (>> 2)

0001 == 1 (>> 3)

Being as you're using a base two system, you can take advantage with certain divisors (integers only!) and just bit-shift. On top of that, I believe most compilers know this and will do this for you.

As for the second part:

(i&0xfffffff8);

Say i = 16

0x00000010 & 0xfffffff8 == 16

(16 / 8) * 8 == 16

Again taking advantage of logical operators on binary. Investigate how logical operators work on binary a bit more for really clear understanding of what is going on at the bit level (and how to read hex).

>> is right shift operation.

If you have a number 8, which is represented in binary as 00001000, shifting bits to the right by 3 positions will give you 00000001, which is decimal 1. This is equivalent to dividing by 2 three times.

Division and multiplication by the same number means that you set some bits at the right to zero. The same can be done if you apply a mask. Say, 0xF8 is 11111000 bitwise and if you AND it to a number, it will set its last three bits to zero, and other bits will be left as they are. E.g., 10 & 0xF8 would be 00001010 & 11111000, which equals 00001000, or 8 in decimal.

Of course if you use 32-bit variables, you should have a mask fitting this size, so it will have all the bits set to 1, except for the three bits at the right, giving you your number - 0xFFffFFf8.

>> shifts the number to the right. Consider a binary number 0001000 which represents 8 in the decimal notation. Shifting it 3 bits to the right would give 0000001 which is the number 1 in decimal notation. Thus you see that every 1 bit shift to the right is in fact a division by 2. Note here that the operator truncates the float part of the result. Therefore i >> n implies i/2^n. This might be fast depending on the implementation of the compiler. But it generally takes place right in the registers and therefore is very fast as compared to traditional divide and multiply.

The answer to the second part is contained in the first one itself. Since division also truncates all the float part of the result, the division by 8 will in theory shift your number 3 bits to the right, thereby losing all the information about the rightmost 3 bits. Now when you again multiply it by 8 (which in theory means shifting left by 3 bits), you are padding the righmost 3 bits by zero after shifting the result left by 3 bits. Therefore, the complete operation can be considered as one "&" operation with 0xfffffff8 which means that the number has all bits 1 except the rightmost 4 bits which are 1000.