整数を何ビットで表せるか

整数を最低何ビットで表せるかを求めます。0,1は1ビット、2,3は2ビット、4/5/6/7は3ビットってな感じです。
ついでに、黒魔術的な実装、よくある実装、酷い実装と、３パターン作ってパフォーマンスの比較もしました。

by kacchan6 04 Oct 2011

• Related works: 1

Tags

bit演算子 optimization 最適化
Embed

package {
    import flash.utils.getTimer;
    import flash.trace.Trace;
    import flash.text.TextField;
    import flash.display.Sprite;
    public class FlashTest extends Sprite {

        private var _tf:TextField;

        private function print(...args):void
        {
            _tf.appendText(args.join(" "));
            _tf.appendText("\n");
        }

        public function FlashTest() 
        {
            var tf:TextField = new TextField();
            tf.width = 465;
            tf.height = 465;
            tf.multiline = true;
            addChild(tf);
            _tf = tf;

            var count:uint = 1000000;
            var t:uint, i:uint;

            t = getTimer();
            for(i = 0; i < count; i++){
                getMinBits1(count);
            }
            print("getMinBits1", getTimer() - t);
            
            t = getTimer();
            for(i = 0; i < count; i++){
                getMinBits2(count);
            }
            print("getMinBits2", getTimer() - t);

            t = getTimer();
            for(i = 0; i < count; i++){
                getMinBits3(count);
            }
            print("getMinBits3", getTimer() - t);
        }
 
        private function getMinBits1(x:uint):uint
        {
            //一番左の立っているビットから右側の全てのビットを1にする
            x |= x >> 1 | 1;
            x |= x >> 2;
            x |= x >> 4;
            x |= x >> 8;
            x |= x >> 16;
            
            //ビットの数を数える(from java.lang.Integer#bitCount)
            x -= x >>> 1 & 0x55555555;
            x = (x & 0x33333333) + (x >>> 2 & 0x33333333);
            x = (x + (x >>> 4)) & 0xf0f0f0f;
            x += x >>> 8;
            x += x >>> 16;
            return x & 0x3f;
        }
 
        private function getMinBits2(x:uint):uint
        {
            if(x  === 0)
            {
                return 1;
            }
            
            var count:uint = 1;
            while((x >>>= 1) !== 0)
            {
                count++;
            }
            
            return count;
        }
 
        private function getMinBits3(x:uint):uint
        {
            return x.toString(2).length;
        }
   }
}