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

by bkzen 05 Oct 2011
Tags

optimization
Embed
// forked from kacchan6's 整数を何ビットで表せるか
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);
            t = getTimer();
            for(i = 0; i < count; i++){
                getMinBits4(count);
            }
            print("getMinBits4", getTimer() - t);
        }
        
        private function getMinBits4(x:uint):uint 
        {
            //一番左の立っているビットから右側の全てのビットを1にする
            x |= x >> 1 | 1;
            x |= x >> 2;
            x |= x >> 4;
            x |= x >> 8;
            x |= x >> 16;
            
            // ビットの数を数える
            x =    (x & 0x55555555) + (x >> 1  & 0x55555555);
            x =    (x & 0x33333333) + (x >> 2  & 0x33333333);
            x =    (x & 0x0f0f0f0f) + (x >> 4  & 0x0f0f0f0f);
            x =    (x & 0x00ff00ff) + (x >> 8  & 0x00ff00ff);
            return (x & 0x0000ffff) + (x >> 16 & 0x0000ffff);
        }
 
        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;
        }
   }
}