変換 - c++ bitset 速度




どのようにして1ビットをセット、クリア、トグルしますか? (18)

どのようにして1ビットをセット、クリア、トグルしますか?

マスクを形成しようとするときに一般的なコーディングの落とし穴に対処するに
1必ずしも十分ではない

numberより広いタイプがあるとき、どんな問題が起こる1か?未定義ビヘイビア(UB)につながる
xシフトには大きすぎる可能性があります。あまりにも大きくない場合でも、最上位ビットを十分に反転することはできません。1 << xx~

// assume 32 bit int/unsigned
unsigned long long number = foo();

unsigned x = 40; 
number |= (1 << x);  // UB
number ^= (1 << x);  // UB
number &= ~(1 << x); // UB

x = 10;
number &= ~(1 << x); // Wrong mask, not wide enough

1が十分に広いことを保証するには:

コードは使用でき1ullまたはpedantically (uintmax_t)1およびコンパイラの最適化をしましょう。

number |= (1ull << x);
number |= ((uintmax_t)1 << x);

またはキャスト - キャスト/レビュー/メンテナンスの問題でキャストを正確かつ最新に保ちます。

number |= (type_of_number)1 << x;

または1、そのタイプのものと同じくらい広い数学演算を強制的に行うことで、やさしく宣伝してくださいnumber

number |= (number*0 + 1) << x;

ほとんどのビット操作と同様に、最高で動作するように符号なしのタイプではなく、署名したもの

C / C ++でどのようにビットをセット、クリア、トグルするのですか?


ビットを設定する

ビット単位のOR演算子( | )を使用してビットを設定します。

number |= 1UL << n;

それはnumber n番目のビットを設定します。 n番目のビットを設定したい場合は、 n-1番目のビットを設定したい場合はn-1にします。

numberunsigned long 1ULL場合は1ULL使用します。 1UL << n宣伝は、 1UL << nを評価してから、定義されていない振る舞いがlong幅を超えてシフトするまで発生しません。 これ以外のすべての例についても同様です。

少しクリアする

ビット単位のAND演算子( & )を使用してビットをクリアします。

number &= ~(1UL << n);

それはnumber n番目のビットをクリアします。 ビット単位のNOT演算子( ~ )を使用してビット列を反転し、次にそれをANDする必要があります。

ビットをトグルする

XOR演算子( ^ )を使用してビットを切り替えることができます。

number ^= 1UL << n;

それはnumber n番目のビットを切り替えます。

少し確認する

あなたはこれを求めていませんでしたが、私はそれを追加するかもしれません。

ビットをチェックするには、番号nを右にシフトし、次にビット単位でANDします。

bit = (number >> n) & 1U;

それはnumber n番目のビットのnumberを可変bit置きbit

n番目のビットをxに変更する

n番目のビットを1または0設定するには、2の補数C ++実装で次のようにします。

number ^= (-x ^ number) & (1UL << n);

ビットnは、 x1場合に設定され、 x0場合にクリアされ0 。 もしxが他の値を持っていれば、あなたはゴミを得るでしょう。 x = !!xは0または1にブールx = !!xを設定します。

これを2の補数の否定動作から独立させるには( -1は1の補数または符号/大きさC ++の実装とは異なり、すべてのビットがセットされます)、符号なしの否定を使用します。

number ^= (-(unsigned long)x ^ number) & (1UL << n);

または

unsigned long newbit = !!x;    // Also booleanize to force 0 or 1
number ^= (-newbit ^ number) & (1UL << n);

ポータブルビット操作には符号なしの型を使用するのが一般的には良い考えです。

また、一般的にはコードをコピー/ペーストしないようにするのが一般的で、多くの人がプリプロセッサマクロ( コミュニティwikiの回答など )やカプセル化を使用することをお勧めします。


任意の型の変数の任意の場所でビットをチェックする:

#define bit_test(x, y)  ( ( ((const char*)&(x))[(y)>>3] & 0x80 >> ((y)&0x07)) >> (7-((y)&0x07) ) )

サンプル使用法:

int main(void)
{
    unsigned char arr[8] = { 0x01, 0x23, 0x45, 0x67, 0x89, 0xAB, 0xCD, 0xEF };

    for (int ix = 0; ix < 64; ++ix)
        printf("bit %d is %d\n", ix, bit_test(arr, ix));

    return 0;
}

注記:これは高速で(柔軟性があるため)、非ブランチであるように設計されています。 Sun Studio 8をコンパイルすると、効率的なSPARCマシンコードが生成されます。 また、amd64でMSVC ++ 2008を使ってテストしました。 ビットの設定とクリアに似たマクロを作ることは可能です。 このソリューションの主な違いは、他の多くのものと比較すると、どのようなタイプの変数であれ、どの場所でも機能するということです。


bitset回答を拡大する:

#include <iostream>
#include <bitset>
#include <string>

using namespace std;
int main() {
  bitset<8> byte(std::string("10010011");

  // Set Bit
  byte.set(3); // 10010111

  // Clear Bit
  byte.reset(2); // 10010101

  // Toggle Bit
  byte.flip(7); // 00010101

  cout << byte << endl;

  return 0;
}

C ++ 11テンプレートバージョン(ヘッダーに入れる):

namespace bit {
    template <typename T1, typename T2> inline void set  (T1 &variable, T2 bit) {variable |=  ((T1)1 << bit);}
    template <typename T1, typename T2> inline void clear(T1 &variable, T2 bit) {variable &= ~((T1)1 << bit);}
    template <typename T1, typename T2> inline void flip (T1 &variable, T2 bit) {variable ^=  ((T1)1 << bit);}
    template <typename T1, typename T2> inline bool test (T1 &variable, T2 bit) {return variable & ((T1)1 << bit);}
}

namespace bitmask {
    template <typename T1, typename T2> inline void set  (T1 &variable, T2 bits) {variable |= bits;}
    template <typename T1, typename T2> inline void clear(T1 &variable, T2 bits) {variable &= ~bits;}
    template <typename T1, typename T2> inline void flip (T1 &variable, T2 bits) {variable ^= bits;}
    template <typename T1, typename T2> inline bool test_all(T1 &variable, T2 bits) {return ((variable & bits) == bits);}
    template <typename T1, typename T2> inline bool test_any(T1 &variable, T2 bits) {return variable & bits;}
}

C言語でこれらの関数のいずれかを試して、nビットを変更してください:

char bitfield;

// Start at 0th position

void chang_n_bit(int n, int value)
{
    bitfield = (bitfield | (1 << n)) & (~( (1 << n) ^ (value << n) ));
}

または

void chang_n_bit(int n, int value)
{
    bitfield = (bitfield | (1 << n)) & ((value << n) | ((~0) ^ (1 << n)));
}

または

void chang_n_bit(int n, int value)
{
    if(value)
        bitfield |= 1 << n;
    else
        bitfield &= ~0 ^ (1 << n);
}

char get_n_bit(int n)
{
    return (bitfield & (1 << n)) ? 1 : 0;
}

ここで私の好きなビット算術マクロは、 unsigned charからsize_tまでの任意の型の符号なし整数配列で動作します(これは効率的に動作する最大の型です):

#define BITOP(a,b,op) \
 ((a)[(size_t)(b)/(8*sizeof *(a))] op ((size_t)1<<((size_t)(b)%(8*sizeof *(a)))))

ビットを設定するには:

BITOP(array, bit, |=);

ビットを消去するには:

BITOP(array, bit, &=~);

ビットをトグルするには:

BITOP(array, bit, ^=);

ビットをテストするには:

if (BITOP(array, bit, &)) ...


このプログラムは、任意のデータビットを0から1または1から0に変更します。

{
    unsigned int data = 0x000000F0;
    int bitpos = 4;
    int bitvalue = 1;
    unsigned int bit = data;
    bit = (bit>>bitpos)&0x00000001;
    int invbitvalue = 0x00000001&(~bitvalue);
    printf("%x\n",bit);

    if (bitvalue == 0)
    {
        if (bit == 0)
            printf("%x\n", data);
        else
        {
             data = (data^(invbitvalue<<bitpos));
             printf("%x\n", data);
        }
    }
    else
    {
        if (bit == 1)
            printf("elseif %x\n", data);
        else
        {
            data = (data|(bitvalue<<bitpos));
            printf("else %x\n", data);
        }
    }
}

これを使って:

int ToggleNthBit ( unsigned char n, int num )
{
    if(num & (1 << n))
        num &= ~(1 << n);
    else
        num |= (1 << n);

    return num;
}

たくさんの動きがある場合は、マスクを使用して全体をすばやくすることができます。 以下の関数は非常に高速で、柔軟性があります(ビットマップのサイズ変更が可能です)。

const unsigned char TQuickByteMask[8] =
{
   0x01, 0x02, 0x04, 0x08,
   0x10, 0x20, 0x40, 0x80,
};


/** Set bit in any sized bit mask.
 *
 * @return    none
 *
 * @param     bit    - Bit number.
 * @param     bitmap - Pointer to bitmap.
 */
void TSetBit( short bit, unsigned char *bitmap)
{
    short n, x;

    x = bit / 8;        // Index to byte.
    n = bit % 8;        // Specific bit in byte.

    bitmap[x] |= TQuickByteMask[n];        // Set bit.
}


/** Reset bit in any sized mask.
 *
 * @return  None
 *
 * @param   bit    - Bit number.
 * @param   bitmap - Pointer to bitmap.
 */
void TResetBit( short bit, unsigned char *bitmap)
{
    short n, x;

    x = bit / 8;        // Index to byte.
    n = bit % 8;        // Specific bit in byte.

    bitmap[x] &= (~TQuickByteMask[n]);    // Reset bit.
}


/** Toggle bit in any sized bit mask.
 *
 * @return   none
 *
 * @param   bit    - Bit number.
 * @param   bitmap - Pointer to bitmap.
 */
void TToggleBit( short bit, unsigned char *bitmap)
{
    short n, x;

    x = bit / 8;        // Index to byte.
    n = bit % 8;        // Specific bit in byte.

    bitmap[x] ^= TQuickByteMask[n];        // Toggle bit.
}


/** Checks specified bit.
 *
 * @return  1 if bit set else 0.
 *
 * @param   bit    - Bit number.
 * @param   bitmap - Pointer to bitmap.
 */
short TIsBitSet( short bit, const unsigned char *bitmap)
{
    short n, x;

    x = bit / 8;    // Index to byte.
    n = bit % 8;    // Specific bit in byte.

    // Test bit (logigal AND).
    if (bitmap[x] & TQuickByteMask[n])
        return 1;

    return 0;
}


/** Checks specified bit.
 *
 * @return  1 if bit reset else 0.
 *
 * @param   bit    - Bit number.
 * @param   bitmap - Pointer to bitmap.
 */
short TIsBitReset( short bit, const unsigned char *bitmap)
{
    return TIsBitSet(bit, bitmap) ^ 1;
}


/** Count number of bits set in a bitmap.
 *
 * @return   Number of bits set.
 *
 * @param    bitmap - Pointer to bitmap.
 * @param    size   - Bitmap size (in bits).
 *
 * @note    Not very efficient in terms of execution speed. If you are doing
 *        some computationally intense stuff you may need a more complex
 *        implementation which would be faster (especially for big bitmaps).
 *        See (http://graphics.stanford.edu/~seander/bithacks.html).
 */
int TCountBits( const unsigned char *bitmap, int size)
{
    int i, count = 0;

    for (i=0; i<size; i++)
        if (TIsBitSet(i, bitmap))
            count++;

    return count;
}

ビット 'n'を16ビット整数に設定するには、次の操作を行います。

TSetBit( n, &my_int);

ビット数が渡すビットマップの範囲内にあることを確認するのはあなた次第です。 リトルエンディアンプロセッサでは、バイト、ワード、ワード、qwordsなどがメモリ内で正しくマップされることに注意してください(リトルエンディアンプロセッサがビッグエンディアンプロセッサよりも優れている主な理由は、ああ、に...)。


より一般的な、任意のサイズのビットマップの場合:

#define BITS 8
#define BIT_SET(  p, n) (p[(n)/BITS] |=  (0x80>>((n)%BITS)))
#define BIT_CLEAR(p, n) (p[(n)/BITS] &= ~(0x80>>((n)%BITS)))
#define BIT_ISSET(p, n) (p[(n)/BITS] &   (0x80>>((n)%BITS)))

ビットをenumにはenumを使う価値があります:

enum ThingFlags = {
  ThingMask  = 0x0000,
  ThingFlag0 = 1 << 0,
  ThingFlag1 = 1 << 1,
  ThingError = 1 << 8,
}

その後、後で名前を使用します 。 書きます

thingstate |= ThingFlag1;
thingstate &= ~ThingFlag0;
if (thing & ThingError) {...}

設定し、クリアしてテストします。 こうすることで、残りのコードから魔法の数字を隠すことができます。

それ以外に、私はJeremyのソリューションを支持します。


ビット演算子: & |使用します|

000b最後のビットを設定するには:

foo = foo | 001b

foo最後のビットをチェックするには:

if ( foo & 001b ) ....

foo最後のビットをクリアするには:

foo = foo & 110b

分かりやすくするためにXXXbを使用しXXXbた。 おそらく、ビットをパックしているデータ構造に応じて、HEX表現で作業するでしょう。


使用される変数

int value, pos;

value - データの
pos - 私たちが設定、クリア、またはトグル
したいビットの位置

value = value | 1 << pos;

少しクリアする

value = value & ~(1 << pos); 

少しトグル

value = value ^ 1 << pos;

標準C ++ライブラリの使用: std::bitset<N>

またはBoostバージョン: boost::dynamic_bitset

あなた自身をロールバックする必要はありません:

#include <bitset>
#include <iostream>

int main()
{
    std::bitset<5> x;

    x[1] = 1;
    x[2] = 0;
    // Note x[0-4]  valid

    std::cout << x << std::endl;
}
[Alpha:] > ./a.out
00010

Boostバージョンでは、 標準ライブラリコンパイル時サイズのビットセットと比較してランタイムサイズのビットセットが可能です。


私が使用するいくつかのマクロは以下のとおりです:

SET_FLAG(Status, Flag)            ((Status) |= (Flag))
CLEAR_FLAG(Status, Flag)          ((Status) &= ~(Flag))
INVALID_FLAGS(ulFlags, ulAllowed) ((ulFlags) & ~(ulAllowed))
TEST_FLAGS(t,ulMask, ulBit)       (((t)&(ulMask)) == (ulBit))
IS_FLAG_SET(t,ulMask)             TEST_FLAGS(t,ulMask,ulMask)
IS_FLAG_CLEAR(t,ulMask)           TEST_FLAGS(t,ulMask,0)

here定義されてhere演算子の1つを使用しhere

ビットを設定するには、used int x = x | 0x?; どこ? バイナリ形式のビット位置です。


int set_nth_bit(int num, int n){

    return (num | 1 << n);
}

int clear_nth_bit(int num, int n){

    return (num & ~( 1 << n));
}

int toggle_nth_bit(int num, int n){

    return num ^ (1 << n);
}

int check_nth_bit(int num, int n){

    return num & (1 << n);
}




bitwise-operators