程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Round Up To Power Of Two

Round Up To Power Of Two

編輯:C++入門知識

Round Up To Power Of Two


這個標題應該說明了我們要做什麼了,中文的意思是找出一個2^n的數,使其不小於給出的數字。舉個例子吧: 如果給一個數字63,那麼我需要獲取不小於63的數字,但是這個數字需要是2的n次方了,所以

  • 63對應的是64(2^6)
  • 64對應的依舊是64(2^6)
  • 100對應的是128(2^7)

    問題來了:

    怎麼快速的計算出這個結果呢?

    可能首先浮現在我們眼前的可能是計算log或者一些其他的一些非位操作的算法,這些算法就不再次說明,來看一下JDK以及android的源碼包中是怎麼來計算的。

    HashMap是一種常用的數據結果,底層是數組與鏈表的結合,為了能夠使key盡量分布均勻,減少碰撞,HashMap的容量都是2^n,容量是2^n的另一個好處是在計算hashcode % size的時候可以使用與操作代替(實現遠離可以google上查看),當我們需要構造一個指定容量(記為sizeA)的HashMap時,HashMap幫我們計算出了不小於sizeA的SizeB,sizeB滿足2^n。
    具體實現在android的java.util.Collections中:

     /**
         * Returns the smallest power of two >= its argument, with several caveats:
         * If the argument is negative but not Integer.MIN_VALUE, the method returns
         * zero. If the argument is > 2^30 or equal to Integer.MIN_VALUE, the method
         * returns Integer.MIN_VALUE. If the argument is zero, the method returns
         * zero.
         *
         * @hide
         */
        public static int roundUpToPowerOfTwo(int i) {
            i--; // If input is a power of two, shift its high-order bit right.
    
            // Smear the high-order bit all the way to the right.
            i |= i >>> 1;
            i |= i >>> 2;
            i |= i >>> 4;
            i |= i >>> 8;
            i |= i >>> 16;
    
            return i + 1;
        }
    

    而在JDK源碼中的實現:

        private static int roundUpToPowerOf2(int number) {
            // assert number >= 0 : number must be non-negative;
            return number >= MAXIMUM_CAPACITY
                    ? MAXIMUM_CAPACITY
                    : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
        }
    
        public static int highestOneBit(int i) {
            // HD, Figure 3-1
            i |= (i >> 1);
            i |= (i >> 2);
            i |= (i >> 4);
            i |= (i >> 8);
            i |= (i >> 16);
            return i - (i >>> 1);
        }
    

    明白原理了麼?可以去小胖軒查看原理講解

     

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved