如何將一個奇數整數向兩個最接近的冪運算

將一個奇數加1或減去1，以使偶數結果更接近最接近的2的冪。如何將一個奇數整數向兩個最接近的冪運算

if (???) x += 1; else x -= 1;// x > 2 and odd

例如，25至47輪朝32，加入一種至25〜31並通過47 23輪從一箇中減去33向下朝向16〜22和49輪向上朝向64〜50

有沒有辦法做到這一點，而沒有找到兩個正在向四捨五入的具體權力。我知道如何使用對數或計數位來獲得兩個特定的冪。

我的具體用例是將奇數大小的輸入分割爲karatsuba乘法。

來源

2013-08-20 drawnonward

所以不做任何改動做甚至整數 – aaronman

對於我的用例，甚至整數不會改變。 – drawnonward

看看我的代碼，它包含日誌索引的解決方案之一，我要使第一個函數爲constexpr，但你得到的點 – aaronman

如果第二個最高有效位被設置，則加，否則減。（x（x >> 1））>（x >> 2））x + = 1;否則x - = 1;

來源

2013-08-20 18:24:47 drawnonward

好吧，我猜這實際上很聰明;） – aaronman

謝謝。在我終於弄明白之前，我做了幾次錯誤的嘗試。 – drawnonward

我認爲在編譯時創建矢量可能在技術上仍然更快，只是sayin – aaronman

保留32位整數的所有2的冪（只有32個條目）對它應該在的位置進行快速二分搜索並不是什麼大事。然後你可以很容易地找出哪個通過從較高和較低的數字中減去並獲得絕對值，數字更接近。然後，您可以輕鬆決定添加哪一個。

您可以通過把你的號碼的數底2，並使用該索引到陣列

更新，以免搜索：提醒這個代碼不徹底的測試。

#include <array> 
#include <cmath> 
#include <iostream> 

    const std::array<unsigned int,32> powers = 
    { 
     1,1<<1,1<<2,1<<3,1<<4,1<<5,1<<6,1<<7,1<<8,1<<9,1<<10,1<<11,1<<12,1<<13,1<<14, 
      1<<15,1<<16,1<<17,1<18,1<<19,1<<20,1<<21,1<<22,1<<23,1<<24,1<<25,1<<26,1<<27, 
      1<<28,1<<29,1<<30,1<<31 -1 
    }; 
    std::array<unsigned int,32> powers_of_two() { 
     std::array<unsigned int,32> powers_of_two{}; 
     for (unsigned int i = 0; i < 31; ++i) { 
      powers_of_two[i] = 1 << i; 
     } 
     powers_of_two[31]=~0; 
     return powers_of_two; 
    } 

    unsigned int round_to_closest(unsigned int number) { 
     if (number % 2 == 0) return number; 
     unsigned int i = std::ceil(std::log2(number)); 
     //higher index 
     return (powers[i]-number) < (number - powers[i-1]) ? 
      ++number:--number; 
    } 

    int main() { 
     std::cout << round_to_closest(27) << std::endl; 
     std::cout << round_to_closest(23) << std::endl; 
     return 0; 
    }

既然不能代表2^31我用最接近的無符號整型它（全1），這意味着1例出所有的人都會產生不正確的結果，我想這不是一個大應對。

我在想，你可以使用一個std::vector<bool>作爲一個非常大的查找表來添加1或減1，看起來像是對我來說似乎是一個操作，似乎運行得相當快的矯枉過正。

來源

2013-08-20 02:42:55 aaronman

正如@aaronman指出的那樣，如果你使用整數，只有最快的方法才能做到這一點，因爲沒有那麼多，所有的2的冪都在表中。通過構造，在一個無符號的32位整數中有32個2的冪（包括數字1），在64位整數中有64個等等。

但是，如果你想在飛行中做一個通用的情況下，你可以很容易地計算任何數字2的周圍冪。在c/C++中：

#include <math.h> 

(...) 

double bottom, top, number, exponent; 

number = 1234; // Set the value for number 

exponent = int(log(number)/log(2.0)); // int(10.2691) = 10 
bottom = pow(2, exponent);    // 2^10 = 1024 
top = bottom * 2;      // 2048 

// Calculate the difference between number, top and bottom and add or subtract 
// 1 accordingly 
number = (top - number) < (number - bottom) ? number + 1 : number - 1;

來源

2013-08-20 10:24:42 rpsml

對於最近的（不是最大或等於） - 看到這一點：

#include <stdio.h> 
#include <stdlib.h> 
int main(int argc, char **argv) { 
    unsigned int val = atoi(argv[1]); 
    unsigned int x = val; 
    unsigned int result; 
    do { 
    result = x; 
    } while(x &= x - 1); 

    if((result >> 1) & val) 
    result <<= 1; 

    printf("result=%u\n", result); 
    return 0; 
}

，如果您需要最大或等於 - 變化：

if((result >> 1) & val)

到

if(result != val)

來源

2013-08-24 01:50:48 maxihatop

如何將一個奇數整數向兩個最接近的冪運算

回答

相關問題