並べ替えられた/並べ替えられていない配列に関するインタビューの質問に出くわすことがよくあり、この配列のある種のプロパティを見つけるように求められます。たとえば、配列内で奇数回出現する数値を検索したり、サイズが 100 万のソートされていない配列内で欠落している数値を検索したりします。多くの場合、質問は O(n) ランタイムの複雑さ、または O(1) スペースの複雑さなどの追加の制約を投稿します。これらの問題はどちらも、ビット単位の操作を使用してかなり効率的に解決できます。もちろん、これらがすべてではありません。このような質問は山ほどあります。
私にとって、ビット単位のプログラミングは、10 進数ではなく 2 進数で機能するため、ハックや直感に基づいているように思えます。実生活でのプログラミング経験がまったくない大学生なので、この種の質問が実際の仕事で実際に人気があるのか 、それともインタビュアーが最も賢い候補者を選ぶために使用する頭の体操にすぎないのか、私は興味があります. それらが実際に役立つ場合、実際にどのようなシナリオで適用できますか?
ビット単位の操作は、実際のプログラミングで一般的で便利ですか?
共通性または適用可能性は、問題によって異なります。
実際のプロジェクトの中には、ビット単位の操作の恩恵を受けるものがあります。
いくつかの例：
ビデオ メモリを直接操作して、画面上の個々のピクセルを設定します。ビデオ メモリでは、すべてのピクセルの色が 1 ビットまたは 4 ビットで表されます。したがって、すべてのバイトで 8 または 2 ピクセルをパックすることができ、それらを分離する必要があります。基本的に、ハードウェアはビット単位の演算の使用を指示します。
個々のビットまたはビットのグループを使用して情報を表現する、ある種のファイル形式 ( GIFなど) またはネットワーク プロトコルを扱っています。データは、ビット単位の操作の使用を決定します。
ある種のチェックサム（おそらく、パリティまたはCRC）またはハッシュ値を計算する必要があり、最も適切なアルゴリズムのいくつかはビットを操作することでこれを行います。
任意精度の算術ライブラリを実装 (または使用) しています。
FFTを実装していて、当然、整数のビットを逆にするか、加算時に反対方向へのキャリーの伝播をシミュレートする必要があります。アルゴリズムの性質上、いくつかのビット単位の操作が必要です。
スペースが不足しており、できるだけ少ないメモリを使用する必要があり、複数のビット値とビットのグループをバイト全体、ワード、ダブルワード、およびクワッドワードに絞り込みます。スペースを節約するために、ビット単位の演算を使用することを選択します。
CPU での分岐/ジャンプはコストがかかるため、コードを分岐なしで一連の命令として実装することでパフォーマンスを向上させたいと考えており、ビット単位の命令が役立ちます。ここでの最も単純な例は、2 つから最小 (または最大) の整数値を選択することです。それを実装する最も自然な方法は、何らかのifステートメントを使用することであり、最終的には比較と分岐を伴います。速度を向上させるために、ビット単位の操作を使用することを選択します。
お使いの CPU は浮動小数点演算をサポートしていますが、平方根などの計算は低速な演算であり、代わりにいくつかの高速で単純な整数演算と浮動小数点演算を使用してシミュレートします。ここでも同じですが、浮動小数点形式のビット表現を操作することでメリットが得られます。
ORCPU またはコンピューター全体をエミュレートしていて、命令をデコードするとき、CPU やハードウェア レジスタの一部にアクセスするとき、ビット単位の命令を単純にエミュレートするときにAND、個々のビット (またはビットのグループ) を操作する必要があります。問題を解決するには、ビット単位の指示が必要です。XORNOT
あなたは、ビット単位のアルゴリズムやトリック、またはビット単位の操作を必要とする何かを Web (ここなど) または本で他の人に説明しています。:)
私は過去 20 年間、上記のすべてを個人的に行ってきました。YMMVだけど。
本当に気にしないのであれば、ユーザーレベルのコードで「回避」できることがよくありますが、メモリ消費が大きな問題になる場合には役立ちます。ハードウェアデバイスや組み込みプログラミング全般を扱う場合、ビット操作が必要になることがよくあります。
さまざまなフラグ スタイルのビットの組み合わせによってアドレス指定可能な、さまざまな構成オプションを持つ I/O レジスタを用意するのが一般的です。または、通常の作業で慣れている最新の PC RAM サイズに比べてメモリが非常に制限されている小さな組み込みデバイスの場合。
また、条件付きコードで表現できるが、より高速なランタイム パフォーマンスが必要な、分岐のない実装を使用したいホット コードの最適化にも非常に便利です。たとえば、与えられた整数に最も近い 2 のべき乗を見つけることは、より一般的なソリューションに対してビット ハックを使用して、一部のプロセッサで非常に効率的に実装できます。
「Hacker's Delight」Henry S. Warren Jr. という素晴らしい本があります。この本には、「現実世界」のコードで発生するさまざまな問題に対して非常に役立つ関数が満載です。同様の内容のオンライン ドキュメントも多数あります。
HAKMEMとして知られる 1970 年代の MIT AI ラボの有名なドキュメントも、別の例です。
ビット演算の使用は、主な関心事に厳密に依存しています。
私はかつて、問題を解決して、一致しない数字のすべての組み合わせを見つけるように求められました。
与えられた i に対して N*i の形式である、それらの中に繰り返し数字があります。
私は突然ビット単位の操作を利用し、すべての数値をより正確に生成しました
時間 、しかし驚いたことに、ビットワイズを使用せずに書き直してコーディングするように求められました
演算子 、人々はそれで可読性を見つけることができないため、多くの人が使用しなければならないコード
さらに。したがって、パフォーマンスが問題になる場合は、 Bitwise を使用してください。
読みやすさが問題になる場合は、それらの使用を減らしてください。
同時に両方が必要な場合は、ビット単位でコードを記述する適切なスタイルに従う必要があります
読みやすい、または理解しやすい方法でオペレーターを操作します。