忌まわしい数字

数値は、バイナリ展開内に奇数の 1 がある場合、奇数とみなされます。最初の 10 個の奇数は、1、2、4、7、10、11、13、14、16、19、21 です。興味深いことに、2 のべき乗はすべて 1 ビットしか設定されていないため、奇数になります。

次の記事では、数字が嫌な数字かどうかを判断する 2 つの方法について詳しく説明します。

＃＃＃問題文＃＃＃

この質問の目的は、指定された数値が忌まわしい数値であるかどうか、つまり、バイナリ展開で奇数のセットビットを持つ正の数値であるかどうかを確認することです。

不快なデジタル例

リーリー リーリー

イラスト

34 のバイナリ表現は 10010 です。

桁数 = 2 を設定します。

1 の数は偶数なので、34 という数字はそれほどひどい数字ではありません。

リーリー リーリー

イラスト

1024 のバイナリ表現は 10000000000 です。

桁数 = 1 を設定します。

1024 は 2 の累乗なので、設定ビットは 1 つだけです。ということで、恐ろしい数字です。

リーリー リーリー

イラスト

(53)

10

= (110101)₂ 桁数 = 4 を設定します。

したがって、これは忌まわしい数字ではありません。

＃＃＃解決＃＃＃

ある数字がヘイトかどうかを判断するには、設定された桁数が奇数か偶数かを知る必要があります。ここでの主なタスクは、数値の 2 進展開で設定された桁数をカウントすることです。次の手法を使用して、桁数を数え、結果が奇数であるか偶数であるかを確認できます。

素朴なアプローチ

の中国語訳は次のとおりです:

素朴なアプローチ

ループ演算子と右シフト演算子を使用して、数値のすべての桁を 1 つずつ繰り返します。

• ビット値が 1 の場合、カウントを 1 つ増やします。

• count の最終値が奇数か偶数かを確認します。

• 答えを表示します。

• 疑似コード

関数 no_of_set_bits()

初期化回数 = 0

• (n > 0)の場合

• リーリー

返品数

• 関数は_odious()

If (カウントが奇数)

• trueを返す

＃＃＃＃＃＃他の＃＃＃＃＃＃

エラーを返す

• 関数 main()

初期化 n

関数呼び出し no_of_set_bits()

• 関数 is_odious()を呼び出します

• 印刷出力

• 例: C プログラム

このプログラムは、数字が不快なものかどうかをチェックします。関数 no_of_set_bits() の各反復の終わりに値を n だけ右にシフトすることにより、ループの各反復の右端のビットをチェックします。
• リーリー ＃＃＃出力＃＃＃ リーリー

  時間と空間の分析

時間計算量: O(log(n))

、n のバイナリ展開には log2n ビットが必要なため、すべてのビットをチェックしてどのビットが設定されているかを確認します。

スペースの複雑さ: O(1)

。余分なスペースが使用されないためです。

ブライアン・カーニハンのアルゴリズム手法

このアルゴリズムを使用すると、数値の設定された桁数をより効率的な方法で計算できます。その後、関数 is_odious() を使用して、その番号が不快なものかどうかを判断できます。 このメソッドの基本原理は、ゼロに達するまでに必要な反復回数を追跡しながら、数値の右端の設定ビットを繰り返しクリアすることです。必要な手順は -

です。

カウントを 0 に初期化します

数値が 0 より大きい場合、数値と 2 の補数の間でビット単位の & を実行して、右端の設定ビットの設定を解除します。

カウントはループ反復ごとに増加します。
最終的なカウントが奇数かどうかを確認します。

• ＃＃＃＃＃＃結果を示す。

• ＃＃＃例＃＃＃

  数値が 10 であるとします。10 を 2 進展開すると 1010 になります。 2 つの設定ビットがあることがわかります。

• ループ反復 1 -
  リーリー
• ループ反復 2 -
  リーリー
反復数 = 設定数 = 2。

疑似コード

関数 no_of_set_bits()

初期化回数 = 0

(n > 0)の場合

n = n & (n-1)

カウントを増やす

返品数
関数は_odious()

前の方法と同じ

関数 main()
前の方法と同じ

例: C プログラム

このプログラムは、すべてのビットの設定を解除するのに必要な反復回数を数えることによって、設定されたビットの数を計算します。ビットをキャンセルするには、n と n-1 に対してビット単位の AND 演算を実行します。これは、n-1 のバイナリ表現により、n の右端の設定ビットとそれに続くすべてのビットが反転されるためです。 リーリー ＃＃＃出力＃＃＃ リーリー

時空分析

時間計算量

- O(log(x))、x は数値に設定された桁数です。設定ビットが 1 つだけの場合、ループは 1 回実行されます。

スペースの複雑さ

- 余分なスペースが使用されないため、O(1)。

上記の方法を比較してください

最初のアプローチは非常に理解しやすいですが、最終結果を生成するには log(n) 回の反復が必要です。一方、2 番目の方法では、log(x) 反復を使用します。ここで、x は数値の 2 進展開で設定された桁数です。したがって、パフォーマンスが向上します。

＃＃＃結論は＃＃＃

この記事では、数値が好ましくないかどうかを確認する 2 つの方法について説明します。また、メソッドの概念、例、使用されるアルゴリズム、C プログラムのソリューション、および各メソッドの複雑さの分析も提供します。また、2 つの方法を比較して、どちらがより効果的かを判断しました。

以上が忌まわしい数字の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。