Crazy Ivan 6023
Beta member
- Messages
- 1
hey guys, i was wondering if any one could show me how to find log2 using only bit operators. here is the jist of what i have thus far, but i still am a little off. you have to find the floor of log 2 of an integer
int log2(int x) {
int logg = 0;
int shifted_x=0;
int shift_val=0;
int big_remove=(255<<8)|255;
/*Isolates the first half of the number and determines if there is a one in
the sequence.*/
shifted_x=x>>16;
//Masks the first half of the bits in the last half.
shifted_x=shifted_x&big_remove;
/*If shifted_x is greater than 0, then 16 will be added to the logg and then
stored as the new shift_val. If not, then the shift_val will be 0*/
shift_val+=(!(!shifted_x))<<4;
logg=shift_val;
/*Shifts the x value by shift_val, which is either 16, or 0.*/
shifted_x=x>>shift_val;
/*Masks the resulting shift with the first quarter. The end result determines
if the bits are in the first quarter, or second quarter if x was shifted and
if the bits are in the thrid quarter or the fourth quarter if x was not
shifted.*/
shifted_x=shifted_x&0xFF;
/*Determines the new shift value. If the result is a non-zero, then then that
value is added to the shift. Therefore the next shift will be either 0, 8,
16, or 24.*/
shift_val+= (!(!shifted_x))<<3;
logg=shift_val;
/*Shifts the x value by shift_val, which is either 0, 8, 16, 24.*/
shifted_x=x>>shift_val;
/*Masks that new value to rid isolate 1/8 of the bit sequence.*/
shifted_x=shifted_x&0xF;
/*Determines the new shift value. This value can either be either 0, 4, 8,
12, 16, 20, 24, 28*/
shift_val+=(!(!shifted_x))<<2;
logg=shift_val;
/*Shifts the x value by the new shift_val*/
shifted_x=x>>shift_val;
/*Masks the new shifted_x value which represents 1/16 of the bit sequence.*/
shifted_x=shifted_x&0x3;
/*Determines the new shift value. This value can either be 0, 2, 4, 6, 8, 10,
12, 14, 16, 18, 20, 22, 24, 26, 28, 30*/
shift_val+=(!(!shifted_x))<<1;
logg=shift_val;
/*Shifts the x value by the new shift_val*/
shifted_x=x>>shift_val;
/*Masks the new shifted_x value which represents 1/32 of the bit sequence*/
shifted_x=shifted_x&0x1;
/*Determines the new shift value. This value can be any value in the range
of 0<=shift_val<=31.*/
shift_val+=!(!shifted_x);
logg=shift_val;
/*Now the function returns the found shifted value which found how many shifts
were needed to find the greatest bit.*/
return logg;
int log2(int x) {
int logg = 0;
int shifted_x=0;
int shift_val=0;
int big_remove=(255<<8)|255;
/*Isolates the first half of the number and determines if there is a one in
the sequence.*/
shifted_x=x>>16;
//Masks the first half of the bits in the last half.
shifted_x=shifted_x&big_remove;
/*If shifted_x is greater than 0, then 16 will be added to the logg and then
stored as the new shift_val. If not, then the shift_val will be 0*/
shift_val+=(!(!shifted_x))<<4;
logg=shift_val;
/*Shifts the x value by shift_val, which is either 16, or 0.*/
shifted_x=x>>shift_val;
/*Masks the resulting shift with the first quarter. The end result determines
if the bits are in the first quarter, or second quarter if x was shifted and
if the bits are in the thrid quarter or the fourth quarter if x was not
shifted.*/
shifted_x=shifted_x&0xFF;
/*Determines the new shift value. If the result is a non-zero, then then that
value is added to the shift. Therefore the next shift will be either 0, 8,
16, or 24.*/
shift_val+= (!(!shifted_x))<<3;
logg=shift_val;
/*Shifts the x value by shift_val, which is either 0, 8, 16, 24.*/
shifted_x=x>>shift_val;
/*Masks that new value to rid isolate 1/8 of the bit sequence.*/
shifted_x=shifted_x&0xF;
/*Determines the new shift value. This value can either be either 0, 4, 8,
12, 16, 20, 24, 28*/
shift_val+=(!(!shifted_x))<<2;
logg=shift_val;
/*Shifts the x value by the new shift_val*/
shifted_x=x>>shift_val;
/*Masks the new shifted_x value which represents 1/16 of the bit sequence.*/
shifted_x=shifted_x&0x3;
/*Determines the new shift value. This value can either be 0, 2, 4, 6, 8, 10,
12, 14, 16, 18, 20, 22, 24, 26, 28, 30*/
shift_val+=(!(!shifted_x))<<1;
logg=shift_val;
/*Shifts the x value by the new shift_val*/
shifted_x=x>>shift_val;
/*Masks the new shifted_x value which represents 1/32 of the bit sequence*/
shifted_x=shifted_x&0x1;
/*Determines the new shift value. This value can be any value in the range
of 0<=shift_val<=31.*/
shift_val+=!(!shifted_x);
logg=shift_val;
/*Now the function returns the found shifted value which found how many shifts
were needed to find the greatest bit.*/
return logg;
