2009-10-11 11 views
7

偶数の場合、いくつかのロジックを書く必要があります。それを均等に分割する2つの最高のパワー。 2^nの最大値はどこですか?ここで入力%2^n == 0?Cの数値を均等に割り算する2の最大出力を計算する

IE: - :バイナリで入力を見たとき、右端の1ビットは、解決策のように見える
入力もなり得るいくつかのビットごとのロジックはそこにのように>出力

4 (0100) -> 4 

8 (1000) -> 8 

12 (1100) -> 4 

14 (1110) -> 2 

24 (11000) -> 8 

etc.... 

に見えます。どのように私はCでこの値を決定するのですか?簡単な解決策がありますか?浮動小数点演算を用いることなく、ジョナサン

答えて

7

Thanks-:

((x^(x - 1)) >> 1) + 1 

簡素化及びエッジケースは、読者の演習として残っています。

+0

X = 24 (24^23)= 24623 24623 >> 1 = 12311 12311 + 1 = 12312 は私が何か間違ったことを計算しましたか? –

+4

Jonathan: '^'はXORなので、 '(24^23)'は15です。 – caf

+0

ところで、xが符号なしなら、特殊な処理が必要な唯一の辺のケースはゼロだと私は信じています。 – caf

17

あなたは2の補数算術演算を想定して喜んでいる場合:

x & -x

あなたはこの種のものの多くを行う(またはあなたはそれが面白い場合でも)場合は、自分自身のコピーを見つけます書籍「ハッカーの喜び」

編集: avakarは、型が符号なしであれば2の補数には依存しないことに注意してください。 によって表現できない 結果が得られた符号なし整数型が 低減モジュロであるため、

オーバーフロー決してでき符号なし オペランドを含む計算:標準の関連セクションは、段落9§6.2.5であります の数値が の最大値よりも大きい数値は、結果として タイプで表すことができます。

「最大値よりも大きい1」は、特にあまのじゃく実装(例えば、バイナリを使用しません。特に、実装)のためのいくつかの余地を残していますが、それに遭遇するかなりそうです。

+1

非常に簡潔で、私は好きです! –

+2

+1。記録のために、2の補数を取る必要はありません。これは、 'x'が符号なし算術型である限り、どのアーキテクチャでも移植可能です。 – avakar

+2

xが1の場合、-xは0xfffffffe、xと-xは0となります。これは質問者が求める答えではありません。 J.F. Sebastianが指摘しているように、x&(〜x + 1)を使ってこの問題を回避することができます。これは2つの演算に拡張された2の補数の否定です。 –

6

我々は(~x + 1)(-x)を置き換えることができます。

x & (~x+1) 

Low Level Bit Hacks You Absolutely Must Knowは、具体的に説明します。

+0

(〜x + 1)は2の補数の-xの定義です。これはxと(-x)よりも少し良い答えです。なぜなら(〜x + 1)はストレートバイナリ算術を使うマシンにしか依存しないからです。 –

3

2^nという形式の数字は、1で2進数で書かれ、その後に0以上の0が続きます。

:たとえば 、1、10、100、1000年、...などが与えられた数を分割2の最高出力を得るために2

のすべての電源は、次の2つの手順を行うことができます

  1. 数値をバイナリ形式で書き込みます。たとえば、番号が168の場合は10101000と入力します。

  2. 10101000.

の最初の部分をオフに当たった後、全てのビット1000(=小数で8)が残っているもの168の場合には1を含ん右側から最初のビット、前

ストライクオフ

あなたの結果は残っています。つまり、数値を2で割った最大の累乗です。

プログラムでは、xを入力番号にします。その後、希望の出力は次のようになります。x - (x^(x-1))

説明:

x^(x-1)【意味XのXORは、x-1]のLSB(最下位ビット)側

x - (x^(x-1))から第1を取り除くを取り除きます残りの部分は、LSB側から最初の1だけを保持します。

関連する問題