13

私の友人は、インタビューで次の質問をされました。すぐに次の解決策を考えましたが、それが正しいかどうかわかりません。

つまり、文字列を 2 つの部分に分割し、両方の部分を 10 進数に変換します。左のサブ配列が 10 進数で 0 の場合、右のサブ配列でバイナリ検索を行い、1 を探します。

それが私のもう一つの質問です。最上位ビットは 2 進数の左端の 1 ですか? 最上位ビットが 0 の場合の例と説明を教えてください。

編集：

以下の回答には少し混乱があるようですので、より正確にするために質問を更新しています。インタビュアーは、「最上位ビットがデータの送信を停止することを示すまでデータを受信するWebサイトを持っています。データ転送を停止するようにプログラムにどのように指示しますか」と述べました

4

7 に答える 7

13

ビットシフトを使用することもできます。擬似コード:

number = gets
bitpos = 0
while number != 0
  bitpos++             # increment the bit position
  number = number >> 1 # shift the whole thing to the right once
end
puts bitpos

数値がゼロの場合、bitpos はゼロです。

于 2013-06-10T15:55:48.843 に答える
12

C ライクな言語命令のみを使用して単語の最上位ビットを見つける (つまり、切り捨てを使用して log2 を計算する) ことは、De Bruijn シーケンスに基づくかなりよく知られた方法を使用して行うことができます。たとえば、32 ビット値の場合

unsigned ulog2(uint32_t v)
{ /* Evaluates [log2 v] */
  static const unsigned MUL_DE_BRUIJN_BIT[] = 
  {
     0,  9,  1, 10, 13, 21,  2, 29, 11, 14, 16, 18, 22, 25,  3, 30,
     8, 12, 20, 28, 15, 17, 24,  7, 19, 27, 23,  6, 26,  5,  4, 31
  };

  v |= v >> 1;
  v |= v >> 2;
  v |= v >> 4;
  v |= v >> 8;
  v |= v >> 16;

  return MUL_DE_BRUIJN_BIT[(v * 0x07C4ACDDu) >> 27];
}

ただし、実際には、より単純な方法 (展開された二分探索など) は通常、同等かそれ以上に機能します。

于 2013-06-10T17:06:16.223 に答える
2

編集された質問は、明確ではありませんが、実際にはまったく異なります。あなたは誰"？ウェブサイトまたはウェブサイトからデータを読み取るプログラムのプログラマーは? あなたが Web サイトの場合は、最上位ビットをセットして値 (しかし、おそらく何バイトか?) を送信することで、プログラムを停止させます。そのビットを OR または ADD するだけです。あなたがプログラマーなら、受け取った値の最上位ビットをテストし、それが設定されたら読み取りを停止します。符号なしバイトの場合、次のようなテストを行うことができます

bool stop = received_byte >= 128;
or
bool stop = received_byte & 128;

署名付きバイトの場合、使用できます

bool stop = received_byte < 0;
or
bool stop = received_byte & 128;

バイトではなく、たとえば 32 ビット ワードを読み取っている場合、128 は に変わります(1 << 31)。

于 2013-06-10T17:10:29.110 に答える
1

これは 1 つのアプローチです (ただし、特にプラットフォームに find-first-one または count-leading-zeros などに対する単一命令ソリューションがある場合は、必ずしも最も効率的ではありません)。整数幅。

int mask = (int)(1U<<31); // signed integer with only bit 32 set
while (! n & mask)        // n is the int we're testing against
  mask >>= 1;             // take advantage of sign fill on right shift of negative number
mask = mask ^ (mask << 1) // isolate first bit that matched with n

最初のビット位置が必要な場合は、31 から始まり、ループの反復ごとに減分される整数カウンターを追加するだけです。

これの欠点の 1 つは、 if です。これはn == 0無限ループなので、事前にゼロをテストしてください。

于 2013-06-10T16:13:28.083 に答える
-1

私はこれがあまりにもトリッキーであることを知りません:)

2 進数を 10 進数に変換してから、数値の 2 を底とする対数を直接返します (float から int に変換)。

解決策は、右から始まる (返された数値 + 1) ビットです。

私が知る限り、あなたの答えは一番左の1です

于 2013-06-10T16:01:33.473 に答える
-2

これは一種のひっかけ問題だと思います。最上位ビットは常に 1 になります :-)。インタビュアーがラテラル シンキングを好む場合、その答えが勝者になるはずです。

于 2013-06-10T15:59:01.573 に答える