14

バイト配列の内容を 12 ビット左にシフトしたい。

たとえば、次の type の配列から始めuint8_t shift[10]ます。

{0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x0A, 0xBC}

左に12ビットシフトすると、次のようになります。

{0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xAB, 0xC0, 0x00}
4

7 に答える 7

8

ポインターをどうぞ！

このコードは、各バイトの 12 ビットを先読みし、適切なビットを前方にコピーすることによって機能します。12 ビットは、次のバイトの下半分 (ニブル) で、2 バイトの上半分が離れています。

unsigned char length = 10;
unsigned char data[10] = {0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0A,0xBC};
unsigned char *shift = data;
while (shift < data+(length-2)) {
    *shift = (*(shift+1)&0x0F)<<4 | (*(shift+2)&0xF0)>>4;
    shift++;
}
*(data+length-2) = (*(data+length-1)&0x0F)<<4;
*(data+length-1) = 0x00;

ジャスティンは次のように書いています：
@Mike、あなたのソリューションは機能しますが、うまくいきません。

まあ、通常のシフト操作はまさにそれを行い（オーバーフローと呼ばれます）、余分なビットを右または左に落とすだけだと思います。必要に応じて簡単に持ち運ぶことができます。シフトを開始する前に 12 ビットを保存するだけです。オーバーフローしたビットを一番下に戻すために、循環シフトが必要な場合がありますか? たぶん、配列を再割り当てして大きくしたいですか？呼び出し元にオーバーフローを返しますか? ゼロ以外のデータがオーバーフローした場合、ブール値を返しますか? キャリーがあなたにとって何を意味するかを定義する必要があります。

unsigned char overflow[2];
*overflow = (*data&0xF0)>>4;
*(overflow+1) = (*data&0x0F)<<4 | (*(data+1)&0xF0)>>4;
while (shift < data+(length-2)) {
    /* normal shifting */
}  
/* now would be the time to copy it back if you want to carry it somewhere */
*(data+length-2) = (*(data+length-1)&0x0F)<<4 | (*(overflow)&0x0F);
*(data+length-1) = *(overflow+1);  

/* You could return a 16-bit carry int, 
 * but endian-ness makes that look weird 
 * if you care about the physical layout */
unsigned short carry = *(overflow+1)<<8 | *overflow;
于 2008-08-27T04:02:45.970 に答える
4

これが私の解決策ですが、さらに重要なのは、問題を解決するための私のアプローチです。

私は問題にアプローチしました

  • メモリセルを描画し、宛先からソースへの矢印を描画します。
  • 上図を表にしました。
  • テーブル内の各行に相対バイト アドレスでラベルを付けます。

これは私にパターンを示しました：

  • iLの下位ニブル (半バイト) とします。a[i]
  • iHの高いニブルにしましょうa[i]
  • iH = (i+1)L
  • iL = (i+2)H

このパターンはすべてのバイトに適用されます。

C に翻訳すると、これは次のことを意味します。

a[i] = (iH << 4) OR iL
a[i] = ((a[i+1] & 0x0f) << 4) | ((a[i+2] & 0xf0) >> 4)

ここで、さらに 3 つの観察を行います。

  • 左から右に割り当てを実行するため、一時変数に値を格納する必要はありません。
  • テールには特別なケース12 bitsがあります。最後はすべてゼロになります。
  • 配列を超えて未定義のメモリを読み取らないようにする必要があります。を超えて読み取ることはないためa[i+2]、これは最後の 2 バイトにのみ影響します。

だから、私たちは

  • N-2 bytes上記の一般的な計算をループして実行することにより、一般的なケースを処理します
  • 設定することにより、最後のバイトの次のバイトを処理しますiH = (i+1)L
  • に設定して最後のバイトを処理します0

alengthを指定するとN、次のようになります。

for (i = 0; i < N - 2; ++i) {
    a[i] = ((a[i+1] & 0x0f) << 4) | ((a[i+2] & 0xf0) >> 4);
}
a[N-2] = (a[N-1) & 0x0f) << 4;
a[N-1] = 0;

配列は だけ左にシフトされ12 bitsます。それは簡単にシフトに一般化することができN bitsます。MM = number of bits modulo 8

一部のマシンでは、ポインターに変換することでループをより効率的にすることができます

for (p = a, p2=a+N-2; p != p2; ++p) {
    *p = ((*(p+1) & 0x0f) << 4) | (((*(p+2) & 0xf0) >> 4);
}

CPU がサポートする最大の整数データ型を使用します。

(私はちょうどこれを入力したので、誰かがコードをレビューする良い機会になるでしょう。特に、ビットいじりは間違いやすいことで知られているためです。)

于 2008-08-27T04:16:29.633 に答える
3

N8 ビット整数の配列でビットをシフトする最良の方法にしましょう。

N            - Total number of bits to shift
F = (N / 8) - Full 8 bit integers shifted
R = (N % 8) - Remaining bits that need to be shifted

ここから、このデータを利用して配列内の int を移動するための最適な方法を見つける必要があると思います。一般的なアルゴリズムは、配列の右側から開始して各整数Fインデックスを移動することにより、完全な整数シフトを適用することです。新しく空いたスペースをゼロで埋めます。最後に、Rすべてのインデックスに対して、再び右からビット シフトを実行します。

ビット単位でシフト0xBCする場合R、ビットごとの AND を実行してオーバーフローを計算し、ビットシフト演算子を使用してシフトできます。

// 0xAB shifted 4 bits is:
(0xAB & 0x0F) >> 4   // is the overflow      (0x0A)
0xAB << 4            // is the shifted value (0xB0)

4 ビットは単純なマスクであることに注意してください: 0x0F または 0b00001111 です。これは簡単に計算でき、動的に作成できます。また、単純な静的ルックアップ テーブルを使用することもできます。

それが十分に一般的であることを願っています。私は C/C++ がまったく得意ではないので、誰かが私の構文をクリーンアップするか、より具体的にすることができます。

おまけ: C を巧みに扱えば、複数の配列インデックスを単一の 16、32、または 64 ビット整数に変換してシフトを実行できる場合があります。しかし、それはおそらくあまり移植性が高くないため、これには反対することをお勧めします。可能な最適化です。

于 2008-08-27T03:40:39.347 に答える
3

ここでは、一時変数を使用した実用的なソリューション:

void shift_4bits_left(uint8_t* array, uint16_t size)
{
    int i;
    uint8_t shifted = 0x00;    
    uint8_t overflow = (0xF0 & array[0]) >> 4;

    for (i = (size - 1); i >= 0; i--)
    {
        shifted = (array[i] << 4) | overflow;
        overflow = (0xF0 & array[i]) >> 4;
        array[i] = shifted;
    }
}

12 ビット シフトの場合、この関数を 3 回呼び出します。

一時変数を使用しているため、Mike のソリューションの方が速いかもしれません。

于 2008-08-27T04:23:41.520 に答える
1

32 ビット バージョン... :-) 1 <= count <= num_words を処理します

#include <stdio.h>

unsigned int array[] = {0x12345678,0x9abcdef0,0x12345678,0x9abcdef0,0x66666666};

int main(void) {
  int count;
  unsigned int *from, *to;
  from = &array[0];
  to = &array[0];
  count = 5;

  while (count-- > 1) {
    *to++ = (*from<<12) | ((*++from>>20)&0xfff);
  };
  *to = (*from<<12);

  printf("%x\n", array[0]);
  printf("%x\n", array[1]);
  printf("%x\n", array[2]);
  printf("%x\n", array[3]);
  printf("%x\n", array[4]);

  return 0;
}
于 2008-08-27T04:19:09.970 に答える
0

@ジョセフ、シフトは12ビット幅であるのに対し、変数は8ビット幅であることに注意してください。あなたのソリューションは、N <= 可変サイズでのみ機能します。

配列が 4 の倍数であると仮定できる場合は、配列を uint64_t の配列にキャストしてから、それに取り組むことができます。4 の倍数でない場合は、できる限り 64 ビット チャンクで作業し、残りを 1 つずつ作業できます。これはもう少しコーディングが必要かもしれませんが、最終的にはよりエレガントになると思います。

于 2008-08-27T03:44:18.200 に答える
0

これを巧妙な問題にするエッジケースがいくつかあります。

  • 入力配列が空である可能性があります
  • 最後のビットと最後から 2 番目のビットは、ゼロ ビットがシフトされているため、特別に処理する必要があります。

次のバイトの下位ニブルを上位ニブルにコピーし、次の次の (+2) バイトの上位ニブルを下位ニブルにコピーする配列をループする単純なソリューションを次に示します。先読みポインタを 2 回逆参照する手間を省くために、「最後」と「次」のバイトを含む 2 要素バッファを維持します。

void shl12(uint8_t *v, size_t length) {
  if (length == 0) {
    return; // nothing to do
  }

  if (length > 1) {
    uint8_t last_byte, next_byte;
    next_byte = *(v + 1);

    for (size_t i = 0; i + 2 < length; i++, v++) {
      last_byte = next_byte;
      next_byte = *(v + 2);
      *v = ((last_byte & 0x0f) << 4) | (((next_byte) & 0xf0) >> 4);
    }

    // the next-to-last byte is half-empty
    *(v++) = (next_byte & 0x0f) << 4;
  }

  // the last byte is always empty
  *v = 0;
}

関数のより多くの部分を連続してアクティブにする境界ケースを考えてみましょう。

  • がゼロのときlengthは、メモリに触れずに救済します。
  • が 1 の場合length、唯一無二の要素を 0 に設定します。
  • が 2 の場合length、最初のバイトの上位ニブルを 2 番目のバイト (つまり、ビット 12 ～ 16) の下位ニブルに設定し、2 番目のバイトをゼロに設定します。ループをアクティブにしません。
  • lengthが 2 よりも大きい場合、ループにヒットし、2 要素バッファー全体でバイトをシャッフルします。

効率が目標である場合、答えはマシンのアーキテクチャに大きく依存します。通常、2 要素のバッファーを維持する必要がありますが、一度に 1 つの機械語 (32/64 ビットの符号なし整数) を処理します。大量のデータをシフトする場合は、最初の数バイトを特殊なケースとして扱う価値があるため、機械語ポインターをワードで整列させることができます。ほとんどの CPU は、アクセスがマシン ワード境界にある場合、より効率的にメモリにアクセスします。もちろん、末尾のバイトも特別に処理する必要があるため、配列の末尾を超えてメモリにアクセスすることはありません。

于 2008-08-27T04:43:40.770 に答える