1

byteビットフラグを保存するために使用しています。相互に排他的な 2 つのフラグの 4 つのペアに分割できる 8 つのフラグ (各ビットに 1 つ) があります。ビットフラグを次のように配置しました。

ABCDEFGH
10011000

フラグ B もセットされている間はフラグ A をセットすることはできません。その逆も成り立つため、フラグ A と B は相互に排他的です。フラグ A と B は両方とも設定を解除できますが、両方を設定することはできません。C 旗と D 旗、E 旗と F 旗、G 旗と H 旗についても同じ規則が適用されます。

現在のテスト ケース (C):

#include <stdio.h>

int check(char b) { // used to check invariant
  return ((b&0xC0)==0xC0||(b&0x30)==0x30||(b&0x0C)==0x0C||(b&0x03)==0x03)?0:1;
}
int main() {
  char input[256] = {
  0x00,0x01,0x02,0x03,0x04,0x05,0x06,0x07,0x08,0x09,0x0a,0x0b,0x0c,0x0d,0x0e,0x0f,
  0x10,0x11,0x12,0x13,0x14,0x15,0x16,0x17,0x18,0x19,0x1a,0x1b,0x1c,0x1d,0x1e,0x1f,
  0x20,0x21,0x22,0x23,0x24,0x25,0x26,0x27,0x28,0x29,0x2a,0x2b,0x2c,0x2d,0x2e,0x2f,
  0x30,0x31,0x32,0x33,0x34,0x35,0x36,0x37,0x38,0x39,0x3a,0x3b,0x3c,0x3d,0x3e,0x3f,
  0x40,0x41,0x42,0x43,0x44,0x45,0x46,0x47,0x48,0x49,0x4a,0x4b,0x4c,0x4d,0x4e,0x4f,
  0x50,0x51,0x52,0x53,0x54,0x55,0x56,0x57,0x58,0x59,0x5a,0x5b,0x5c,0x5d,0x5e,0x5f,
  0x60,0x61,0x62,0x63,0x64,0x65,0x66,0x67,0x68,0x69,0x6a,0x6b,0x6c,0x6d,0x6e,0x6f,
  0x70,0x71,0x72,0x73,0x74,0x75,0x76,0x77,0x78,0x79,0x7a,0x7b,0x7c,0x7d,0x7e,0x7f,
  0x80,0x81,0x82,0x83,0x84,0x85,0x86,0x87,0x88,0x89,0x8a,0x8b,0x8c,0x8d,0x8e,0x8f,
  0x90,0x91,0x92,0x93,0x94,0x95,0x96,0x97,0x98,0x99,0x9a,0x9b,0x9c,0x9d,0x9e,0x9f,
  0xa0,0xa1,0xa2,0xa3,0xa4,0xa5,0xa6,0xa7,0xa8,0xa9,0xaa,0xab,0xac,0xad,0xae,0xaf,
  0xb0,0xb1,0xb2,0xb3,0xb4,0xb5,0xb6,0xb7,0xb8,0xb9,0xba,0xbb,0xbc,0xbd,0xbe,0xbf,
  0xc0,0xc1,0xc2,0xc3,0xc4,0xc5,0xc6,0xc7,0xc8,0xc9,0xca,0xcb,0xcc,0xcd,0xce,0xcf,
  0xd0,0xd1,0xd2,0xd3,0xd4,0xd5,0xd6,0xd7,0xd8,0xd9,0xda,0xdb,0xdc,0xdd,0xde,0xdf,
  0xe0,0xe1,0xe2,0xe3,0xe4,0xe5,0xe6,0xe7,0xe8,0xe9,0xea,0xeb,0xec,0xed,0xee,0xef,
  0xf0,0xf1,0xf2,0xf3,0xf4,0xf5,0xf6,0xf7,0xf8,0xf9,0xfa,0xfb,0xfc,0xfd,0xfe,0xff};

  char truth[256] = {
  1,1,1,0,1,1,1,0,1,1,1,0,0,0,0,0,
  1,1,1,0,1,1,1,0,1,1,1,0,0,0,0,0,
  1,1,1,0,1,1,1,0,1,1,1,0,0,0,0,0,
  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
  1,1,1,0,1,1,1,0,1,1,1,0,0,0,0,0,
  1,1,1,0,1,1,1,0,1,1,1,0,0,0,0,0,
  1,1,1,0,1,1,1,0,1,1,1,0,0,0,0,0,
  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
  1,1,1,0,1,1,1,0,1,1,1,0,0,0,0,0,
  1,1,1,0,1,1,1,0,1,1,1,0,0,0,0,0,
  1,1,1,0,1,1,1,0,1,1,1,0,0,0,0,0,
  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};

  int i,r;
  int f = 0;
  for(i=0; i<256; ++i) {
    r=check(input[i]);
    if(r != truth[i]) {
      printf("failed %d : 0x%x : %d\n",i,0x000000FF & ((int)input[i]),r);
      f += 1;
    }
  }
  if(!f) { printf("passed all\n");  }
  else   { printf("failed %d\n",f); }
  return 0;
}

上記のcheck()メソッドは現在、すべてのテスト ケースに合格しています。ビットいじりハックを使用して、この不変式が真であることを確認するより効率的な方法があるかどうかを知りたいです。この不変条件を 1 秒間に何度もチェックする必要がある場合があるため、効率が重要です。新しい配置が、元の配置ではできなかったちょっとしたハックを可能にする場合は、フラグの配置を変更したいと思います。

順列例: ABCDEFGH-->AHBGCFDE

4

3 に答える 3

6

私はこれをプロファイリングしていないので、約束はできませんが、試すことができます：

int check(char b)
{
    return ! ( (b << 1) & b & 0xaa );
}

!0 以外 (1 だけではない) を失敗として受け入れ、0 を合格として受け入れると、反転をなくすことができます。

または、すでに生成したルックアップ テーブルを使用することもできます。

int check(char b)
{
    return truth[(unsigned char)b];
}

何を試しても、プロフィールを作成してください。

（ああ、ビットシフトやブール値などの動作はより適切に定義されているため、このようなビットフィールドを格納するには、符号付き文字ではなく符号なし文字を使用することをお勧めします。ほとんどのコンパイラはおそらく期待どおりに動作しますが、より安全です申し訳ありません）。

于 2013-01-20T19:08:03.183 に答える
1

基本的に 4 つのトライステート値があります。オプション 1 が設定されているか、オプション 2 が設定されているか、どちらも設定されていません。これらのトライステートを追跡するために、構造体でビット フィールドを使用して、それぞれ 2 ビットの nsigned 整数を明示的に取得することを検討することをお勧めします。

struct Flags {
    unsigned opt1: 2;
    unsigned opt2: 2;
    unsigned opt3: 2;
    unsigned opt4: 2;
};
const unsigned NEITHER = 0;
const unsigned FIRSTOPT = 1;
const unsigned SECONDOPT = 2;
const unsigned INVALIDOPT = 3;

この設定では、質問は 4 つのフィールドすべてが INVALIDOPT と等しくないことを確認することに要約されます。したがって、チェック機能は次のようになります

bool IsValid(struct Flags flags) {
    return flags.opt1 != INVALIDOPT &&
           flags.opt2 != INVALIDOPT &&
           flags.opt3 != INVALIDOPT &&
           flags.opt4 != INVALIDOPT;
}

これは、ビットをいじってどのオプションを選択するかを設定する代わりに、名前付き定数を使用して通常の変数の読み取りと書き込みを実行できることも意味します。はるかに簡単で安全なはずです。

お役に立てれば！

于 2013-01-20T19:08:23.480 に答える
0

そもそもそれを防ぐには：

#define NONE_SET 0 // 00
#define FIRST_SET 1 // 10
#define SECOND_SET 2 // 01

int magic(int AB, int CD, int EF, int GH) {
  return (((AB*3+CD)*3+EF)*3+GH)*3
}

さらに良いのは、 s のenum代わりにan を使用することです。#define

呼び出し例 (例: ABCDEFGH=10000100)

int magic_number = magic(FIRST_SET, NONE_SET, SECOND_SET, NONE_SET);

少しいじる必要はありません。いくつかの乗算だけです。（これは明らかに自動化できます）

バイト内のビットのペアが両方とも設定されていないかどうかを確認したいだけの場合:

uint8_t in; // the input byte
uint8_t out = in & (in >> 1) & 0x55; 
// if out != 0, the invariant is violated

注: 0x55 はバイナリで 01010101 です (つまり、BC のような隣接するペアをマスクして、AB や CD のようなものだけを残します)

于 2013-01-20T19:08:08.987 に答える