ハッカーのたのしみ

■ x以下で最大の２のべき乗を求める分岐を用いない方法

#include <stdio.h>

unsigned flp2( unsigned );

void main ( void )
{
	unsigned int x = 67;    /* 試しに67 */
	
         /* ※　↓x:67 flp2( x ):64 となります。*/
	printf( " x:%u, flp2( x ):%u\n", x, flp2( x ) );
}


/* x以下で最大の２のべき乗を求める分岐を用いない方法 */
unsigned flp2( unsigned x )
{
	x = x | ( x >> 1  );
	printf( "%u\n", x );    /* ※99  */
	
	x = x | ( x >> 2  );
	printf( "%u\n", x );    /* ※123 */
	
	
	x = x | ( x >> 4  );
	printf( "%u\n", x );    /* ※127 */
	
	x = x | ( x >> 8  );
	printf( "%u\n", x );    /* ※127 */
	
	x = x | ( x >> 16 );
	printf( "%u\n", x );    /* ※127 */
	
	return( x - ( x >> 1 ) );
}

2のべき乗でシフトしORをとる、ということをintサイズ分繰り返し、最後に1bit右シフトしたもので引く。という感じか。

ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか