交互ビットスミアリング

前書き

この問題は、整数バイナリ表現の末尾の0を 010101 ... に設定する必要があります。

整数 400 が与えられた場合、最初のステップはバイナリに変換することです:

110010000

見て分かるように、5番目のビットは最下位の 1 ビットなので、そこから始めて下位0を
0101 で置き換えます。

110010101

Finally we convert that back to decimal: 405

チャレンジ

与えられた正の整数は、上で定義されたプロセスの対応する結果値を返します。

ルール

  • このシーケンスは少なくとも1つの 1
    ビットを持つ整数に対してのみ定義されるため、入力は常に1以上になります。
  • 文字列、数字のリスト(10進数)として入力できます。
  • 無効な入力を処理する必要はありません

テストケース

Here are some more テストケース with the intermediary steps (you don’t
have to print/return these):

In -> … -> … -> Out
1 -> 1 -> 1 -> 1
2 -> 10 -> 10 -> 2
3 -> 11 -> 11 -> 3
4 -> 100 -> 101 -> 5
24 -> 11000 -> 11010 -> 26
29 -> 11101 -> 11101 -> 29
32 -> 100000 -> 101010 -> 42
192 -> 11000000 -> 11010101 -> 213
400 -> 110010000 -> 110010101 -> 405
298 -> 100101010 -> 100101010 -> 298
ベストアンサー

Python
3
, 20 bytes

lambda n:(n&-n)//3+n

3-お試しください!

説明

192 を例に取ってください。バイナリ形式は 11000000 で、
11010101 に変換する必要があります。

数字に 10101 を追加する必要があることに注意してください。これは(4 ^
3-1)/(4-1)
のような閉じた形式を持つ幾何学的系列( 4 ^ 0 + 4 ^ 1 + 4 ^
2
コード>。これは 4 ^ 3//3
と同じです。//は整数除算を示します。

101010 だった場合でも、幾何学的系列( 2×4 ^ 0 + 2×4 ^ 1 +
2×4 ^ 2
code> 2×4 ^ 3//3 になります。

Anyway, 4^3 and 2×4^3 would just be
the least significant bit, which we obtain by
n&-n:

n の補数は 00111111 です。追加すると
01000000 になり、最下位桁の n = 11000000 と重なるだけです。
“補完と追加”は単なる否定であることに注意してください。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です