By the way, is

`n`

a signed or an unsigned number? At first, I think that `n`

is `signed`

and this is the reason for the extra instructions for the division (sign extension and substraction). If n would have been `unsigned`

, then my guess is that the code would have been identical.By the way, in both cases

`SAR`

(Shift Arithmetic Right) instruction is used. This confirm the fact that number `n`

is `signed`

. I think that extra instructiona are required for rounding purpose of odd negative numbers (by adding 1).[ --- Improved anwser --- ]

If n can be negative, division might be faster on average simply because it will loop less often in some cases.

If n can be negative, division might be faster on average simply because it will loop less often in some cases.

For example using division, we have 5 steps starting with -31 before reaching 0.

```
1: -31 / 2 = -15
2: -15 /2 = -7
3: -7 /2 = -3
4: -3 / 2 = -1
5: -1 / 2 = 0
```

If instead, we uses >>, we have 6 steps in that case:

```
1: -31 >> 1 = -16
2: -16 >> 1 = -8
3: -8 >> 1 = -4
4: -4 >> 1 = -2
5: -2 >> 1 = -1
6: -1 >> 1 = 0
```

For positive or even number, we would expect shift to be a bit faster when n is signed (and exactly the same if n would have been unsigned).

If this not the case, then it might be some obsure reason related to caching or jump prediction or pipelining.

By the way, if n was made unsigned, there might be a gain and if n is never negative, then the result would be the same. If n is always a power of 2, then n should really be unsigned.

**Finally, if you really want to optimize that function and you expect n to be greater than 255 (for example), then you should split the number into parts.**

Something like:

```
unsigned int n = /* some power of 2 */
int exp = 0;
if (n > 0xFFFF) { exp = 16; n = n / 65536; }
if (n > 0xFF) { exp += 8; n = n / 256; }
if (n > 0xF) { exp += 4; n = n / 16; }
if (n > 0x3) { exp += 2; n = n / 4; }
if (n > 0x1) { exp += 1; n = n / 2; }
;
```

Except for very small n (say less than 32), that code would be faster.

If n is not a power of 2, then the code should give the maximum exponent such that 2^exp is less or equal to n.

**And still faster:**

If you compile in 32 bits under Visual C++, you can uses assembler

`BSR`

instruction. Alternatively, you can uses intrinsic function (

`_BitScanReverse`

under Visual C++ 2005 and above).For other compilers, you might have similar options.

**Conclusion**

In any cases, you should uses unsigned number if n is always positive as it will lead to more efficient code. Intrisic function is the best option if you really need performance.

If you want portable code that should be fast, then my unrolled code above would be the best option particulary if n is expected to be larger than 1 byte.

`n >>= i`

:DAs mentioned it's likely due to optimization, maybe compile without optimization or don't use a literal 2.

CDQ - Converts Double Word EAX to Quad Word EDX:EAX.

SUB - Subtracts EDX (Source) from EAX (Destination)

SAR - Shift Arithmetic Right

See http://web.itu.edu.tr/~kesgin/mul06/intel/

Also you can uses Google to find articles on finding most significant bit (there are a lot of them).