本文共 4398 字,大约阅读时间需要 14 分钟。
给定数字的b+树创建
Problem statement:
问题陈述:
Find Next and previous power of two of a given number
查找给定数字中两个的下一个和上一个幂
Next power of two
下一个二的幂
Example(1): input: 22 output: 32 ( as 32 is 2^5) Example(2): input: 54 output: 64 (as 64 is 2^6)
Previous power of two
以前的二的幂
Example(1): input: 22 output: 16 Example(2): input: 54 output: 32
We can solve this problem using bit manipulation easily.
我们可以使用位操作轻松解决此问题。
Just have a look on the binary representation of the number which is a power of 2.
只需看一下数字的二进制表示形式就是2的幂。
power of 2 Binary Representation 1 1 2 10 4 100 8 1000 16 10000 32 100000 64 1000000 128 10000000
As we can see every number have only their left most bit set (i.e 1) and rest are unset (i.e 0).
我们可以看到,每个数字只有最左边的位(即1)被置位,其余的都未置位(即0)。
If we somehow, can unset all bits except the left most bit in a binary representation of number we will get previous power of two of the given number.
如果我们以某种方式可以取消设置二进制数字表示形式中除最左边的位以外的所有位,我们将获得给定数字的2的幂。
Example:
例:
Number Binary representation previous power of two 7 111 100 (i,e 4) 25 11001 10000 (i.e 16) 95 1011111 1000000 (i,e 64)
We will use Bitwise AND ( & ) operation to clear bits.
我们将使用按位与(&)操作清除位。
Here is Algorithm to get previous power of 2 of n,
这是获取n的2的先前幂的算法,
step 1: n = n & n-1step 2: if n is power of two , n is our desired result,go to step 3. else go to step 1.step 3: print n and stop
Explanation:
说明:
let n = 27 ( 11011 in binary)n-1 = 26 ( 11010 in binary)n&n-1 = 26as 26 is not a power of 2 so we will repeat above step againnew n = 26n = 26 ( 11010 in binary)n-1 = 25 ( 11001 in binary)n&n-1 = 24 ( 11000 in binary)as 24 is not a power of 2 so we will repeat above step againnew n=24n = 24 ( 11000 in binary)n-1 = 23 ( 10111 in binary)n&n-1 = 16 ( 10000 in binary)as 16 is a power of 2 so this is our answer
To get next power of two, all we have to do is to find a binary number greater than the given number having only left most bit set.
要获得2的下一个幂,我们要做的就是找到一个比给定数字大的二进制数,该二进制数只剩下最左边的位。
We can use left shift operator ( << )to generate a number having only its left most bit set.
我们可以使用左移运算符(<<)来生成仅设置其最左位的数字。
Left shift operation example:
左移操作示例:
1 << 5This means that shift 1 left by 5 place1 in binary is represented as 1so after shifting 1 by 5 place left, output will be 100000 ( i.e 32 in decimal)5 << 2This means that shift 5 left by 2 place5 in binary is represented as 101so after shifting it by 2 place to left,output will be 10100 ( i.e 20 in decimal)
Note: In each shift right most bit will be set to 0;
注意:在每个移位右移的大多数位将被设置为0;
Program:
程序:
</ s> </ s> </ s>#includeusing namespace std;long int nextPowerOfTwo ( int n ){ // Result is intialized as 1 long int value = 1; // The following while loop will run until we // get a number greater than n while(value<=n) { // value will be left shifted by 1 place in each iteration value=value << 1; } return value ;}int previousPowerOfTwo(int n ){ // If n is already a power of two, we can simply shift it right // by 1 place and get the previous power of 2 // (n&n-1) will be 0 if n is power of two ( for n > = 2 ) // (n&&!(n&(n-1))) condition will take care of n < 2; if((n&&!(n&(n-1)))==1) { return (n>>1); } // This while loop will run until we get a number which is a power of 2 while(n&n-1) { // Each time we are performing Bit wise And ( & )operation to clear bits n=n&n-1; } return n ;}int main(){ int n; cout << "Enter Number\n"; cin >> n; long int num=nextPowerOfTwo(n); cout << "Next power of two : " << num ; cout << "\n\nEnter Number\n"; cin >> n; num=previousPowerOfTwo(n); cout << "Previous power of two : " << num ; return 0;}
Output
输出量
Enter Number 34 Next power of two : 64 Enter Number 34 Previous power of two : 32 Process returned 0 (0x0) execution time : 7.681 s Press any key to continue.
翻译自:
给定数字的b+树创建
转载地址:http://fzxzd.baihongyu.com/