0

将奇数加一或减一，以使偶数结果更接近于最接近的 2 次方。

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

例如，25 到 47 舍入到 32，将 1 加到 25 到 31 并从 33 到 47 减去 1。23 向下舍入到 16 到 22，49 向上舍入到 64 到 50。

有没有办法做到这一点，而无需找到正被四舍五入的两个的具体力量。我知道如何使用对数或计数位来获得 2 的比幂。

我对此的具体用例是将奇数大小的输入拆分为 karatsuba 乘法。

4

4 回答 4

4

如果设置了第二个最高有效位，则加法，否则减法。

如果 ( (x&(x>>1)) > (x>>2) ) x += 1; 否则 x -= 1;

于 2013-08-20T18:24:47.887 回答
1

为 32 位整数（只有 32 个条目）保留所有 2 的幂并不是什么大问题通过从较高和较低的数字中减去并获得abs。然后，您可以轻松决定添加哪个。

您可以通过获取您的数字的日志基数 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 个案例会产生不正确的结果，我认为这没什么大不了的。

我在想你可以使用 astd::vector<bool>作为一个非常大的查找表来加 1 或减 1，这对我来说似乎有点过分了，因为这个操作似乎运行得很快。

于 2013-08-20T02:42:55.897 回答
0

正如@aaronman 指出的那样，如果您正在使用整数，那么最快的方法是在表中拥有 2 的所有幂，因为没有那么多。通过构造，在无符号 32 位整数中有 2 的 32 次幂（包括数字 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-20T10:24:42.510 回答
0

对于最近的（不是最大或相等的） - 请参见：

#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-24T01:50:48.040 回答