CareerCup

a & (((sizeof(a)*8)-1)<<1)

input : a
(a & 0x8000)? print("MSB : 1") : print("MSB : 0")

or

printf("MSB : %d", a >> 12);

My Take:
Do right bit shift till there are no bits left.
Let number x has n bits then x>>1 will be O(n).
Any better solution than this ?

Assuming uint32 value.
Do a binary search.
Take masks and AND with the uint32.

Ex: uint16 value = 0000 0101 1100 0010
first step: mask the LSB 8 bit and MSB 8 bits
MSB: 0000 0101
LSB: 1100 0010
MSB > 0 => repeat first step on MSB

MSB: 0000
LSB: 0101
MSB == 0 => repeat first step on LSB

MSB: 01
LSB: 01
MSB > 0 => repeat first step on MSB

MSB: 0
LSB: 1
MSB == 0 => repeat first step on LSB

LSB == single bit. This is the MSB of uint16

The complexity is O(log n)

Please add your thoughts.

how to find the msb in smallest no. of steps

Did the question mean to find the position of MSB coz the bits has values 0 and 1. we dont consider the 0 values so did this question needs to find the position of first 1 in MSB.

it was for msb value 1

Algo - O(1) but requires precomputed Table

1>Reverse in O(1) using Table
2>Find LSB in O(1)

Sorry I got it all wrong .....

while(a&=(a-1)) ++msb_cnt++;

This is equivalent to running a for loop with right shifting the left most bit by 1 each time. Complexity would be O(n) (i.e looping through all the bits)

Using asm
MOV A,NUMBER
RAR A
JC
If msb is 1 then JC excute else not

log( number & (number+1))........take base 2

Wouldn't MSB be 1 for all numbers except 0...

Isn't the MSB just the sign of the number?

floor(log2(number))