0

偶数の結果が最も近い 2 の累乗に近くなるように、奇数の整数に 1 を加算または 1 を減算します。

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

たとえば、25 から 47 は 32 に丸められ、25 から 31 に 1 が加算され、33 から 47 から 1 が減算されます。

丸められる特定の 2 の累乗を見つけずにこれを行う方法はありますか。対数またはカウント ビットを使用して、特定の 2 のべき乗を取得する方法を知っています。

これに対する私の具体的な使用例は、奇数サイズの入力をカラツバ乗算に分割することです。

4

4 に答える 4

1

32 ビット整数 (32 エントリのみ) のすべての 2 のべき乗を保持することは大したことではありません。それが存在するはずの場所をすばやくバイナリ検索します。そうすれば、どの数値に近いかを簡単に把握できます。高い数値と低い数値から減算して腹筋を取得します。次に、どちらに追加するかを簡単に決定できます。

数値の基数 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 を表すことができないので、それに最も近い unsigned int (すべて 1) を使用しました。これは、すべてのケースのうち 1 つのケースが間違った結果を生成することを意味しますが、それは大したことではないと考えました。

std::vector<bool>私は、1 を足したり 1 を引いたりするために、非常に大きなルックアップ テーブルとして aを使用できると考えていました。

于 2013-08-20T02:42:55.897 に答える
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 に答える