Питання Як ви встановлюєте, очищаєте та перемикаєте один біт?


Як ви встановлюєте, очищаєте та переключаєтесь у C / C ++?


2053
2017-09-07 00:42


походження


Прочитай це: graphics.stanford.edu/~seander/bithacks.html і, коли ви освоїте це, прочитайте цей: realtimecollisiondetection.net/blog/?p=78 - ugasoft
Ви також можете бути зацікавлені у перевірці The Bit Twiddler, Bit Twiddling Hacks, і Загальні магічні алгоритми.
Ця посилання допомогла мені зрозуміти, як ці операції справді працюють - cs.umd.edu/class/sum2003/cmsc311/Notes/BitOp/setBitI.html Тут ви можете знайти цікавіші операції - cs.umd.edu/class/sum2003/cmsc311/Напримітки - rajya vardhan
Я легко собі уявляю це було не для самого питання, а для створення дуже корисного довідника. Враховуючи, що я приїхав сюди, коли мені потрібно трохи інформації, у всякому разі. - Joey van Hummel
@glglgl / Jonathon це має достатньо значення для C ++, щоб бути позначені як такі. Це історичне питання з великою кількістю трафіку, і тег C ++ допоможе іншим зацікавленим програмістам знайти його через пошук Google. - Luchian Grigore


Відповіді:


Налаштування трохи

Використовуйте побітовий АБО оператор (|), щоб встановити трохи.

number |= 1UL << n;

Це буде встановлювати nй біт number.

Використовуйте 1ULL якщо number є ширшим, ніж unsigned long; сприяння 1UL << n не відбувається, тільки після оцінки 1UL << n де невизначена поведінка зміщується більш ніж на ширину a long. Те ж саме стосується всіх інших прикладів.

Почистивши трохи

Використовуйте побітовий оператор AND (&), щоб очистити трохи.

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

Це очистить nй біт number. Ви повинні інвертувати бітовий рядок з побічним НЕ оператором (~), а потім і це.

Трохи трохи

Оператор XOR (^) можна використовувати для перемикання трохи.

number ^= 1UL << n;

Це буде перемикати nй біт number.

Перевірка трохи

Ви не просили цього, але я міг би також додати його.

Щоб трохи перевірити, зсуньте число n праворуч, а потім побітне І це:

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

Це додасть вартість nй біт number в змінну bit.

Зміна нтой біт до х

Налаштування nТой біт до того ж 1 або 0 може бути досягнуто з наступним на 2 доповнення C ++ реалізації:

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

Біт n буде встановлено, якщо x є 1, і очищено, якщо x є 0. Якщо x має якесь інше значення, ви отримуєте сміття. x = !!x буде booleanize до 0 або 1.

Зробити це незалежним від 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);

Як правило, корисно використовувати типи без підпису для переносних бітних маніпуляцій.

Як правило, непогано рекомендується не копіювати / вставляти код взагалі, і тому багато людей використовують макроси препроцесорів (наприклад, спільнота вікі відповісти далі) або якийсь інкапсуляція.


3003
2017-09-07 00:50



Я хотів би зазначити, що на платформах, що мають власну підтримку бітових / мікроконтролерів (наприклад, мікроконтролерів AVR), компілятори часто перекладуть "myByte | = (1 << x)" в набір інструкцій для набору чи очищення біт, коли x константа, ex: (1 << 5), або const unsigned x = 5. - Aaron
біт = число & (1 << x); не поставить значення bit x у біт, якщо біт не має типу _Bool (<stdbool.h>). В іншому випадку bit = !! (число & (1 << x)); буде .. - Chris
чому ти не міняєш останній на bit = (number >> x) & 1 - aaronman
1 є int буквальний, який підписаний. Тому всі операції тут працюють за підписаними номерами, що не є чітко визначеними стандартами. Стандарти не гарантують двох додатків або арифметичних зрушень, тому їх краще використовувати 1U. - Siyuan Ren
я віддаю перевагу number = number & ~(1 << n) | (x << n); за зміну n-го біта на х. - Eliko


Використання стандартної бібліотеки C ++: std::bitset<N>.

Або Підвищити версія: 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 дозволяє встановити біт сегмент у порівнянні з a стандартна бібліотека компіляція часу, розмір бітсета.


383
2017-09-18 00:34



+1 Не те, що std :: bitset можна використовувати з "C", але, як автор позначив його питання "C ++", AFAIK, ваша відповідь найкраще тут ... std :: vector <bool> - це ще один спосіб, якщо хтось знає його плюси і мінуси - paercebal
@ andrewdotnich: вектор <bool> є (на жаль) спеціалізацією, яка зберігає значення як біти. Побачити gotw.ca/publications/mill09.htm для отримання додаткової інформації ... - Niklas
Можливо, ніхто не згадав про це, оскільки його було позначено вбудованим. У більшості вбудованих систем ви уникаєте STL, як чума. І підтримка підтримки - швидше за все, дуже рідкісна птиця, яку можна знайти серед більшості вбудованих компіляторів. - Lundin
@Мартин Це дуже вірно. Окрім конкретних виконавців, таких як STL та шаблони, багато вбудованих систем навіть уникають цілісних стандартних бібліотек, оскільки вони є такими болями для перевірки. Більша частина вбудованої галузі охоплює такі стандарти, як MISRA, для якої потрібні статичні інструменти аналізу коду (будь-які професіонали програмного забезпечення повинні використовувати такі інструменти, а не тільки вбудовані люди). Як правило, у людей кращі речі, ніж робити статичний аналіз через всю стандартну бібліотеку - якщо його вихідний код навіть доступний для них на конкретному компіляторі. - Lundin
@ Lundin: Ваші заяви є надмірно широкими (таким чином, непотрібно сперечатися). Я впевнений, що я можу знайти ситуації, якщо вони правдиві. Це не змінює мого початкового моменту. Обидва ці класи чудово підходять для використання в вбудованих системах (і я знаю, що вони використовуються). Ваша початкова точка про те, що STL / Boost не використовується для вбудованих систем, також неправильна. Я впевнений, існують системи, які не використовують їх, і навіть ті системи, які їх використовують, вони розумно використовуються, але говорять, що вони не використовуються, просто не правильно (тому що існують системи, в яких вони використовуються). - Martin York


Інший варіант полягає у використанні бітних полів:

struct bits {
    unsigned int a:1;
    unsigned int b:1;
    unsigned int c:1;
};

struct bits mybits;

визначає 3-бітове поле (власне, це три 1-бітних поля). Бітові операції тепер стали трохи (ха-ха) простішими:

Щоб встановити або очистити трохи:

mybits.b = 1;
mybits.c = 0;

Щоб переключитися трохи:

mybits.a = !mybits.a;
mybits.b = ~mybits.b;
mybits.c ^= 1;  /* all work */

Перевірка трохи:

if (mybits.c)  //if mybits.c is non zero the next line below will execute

Це працює лише з бітними полями з фіксованим розміром. В іншому випадку вам слід вдатися до методів дрібниць, описаних у попередніх публікаціях.


213
2017-09-11 00:56



Я завжди знайшов використання бітових полів - це погана ідея. Ви не можете контролювати порядок, в якому розподіляються біти (зверху або внизу), що робить неможливим серіалізацію значення стабільним / портативним способом за винятком bit-at-a-time. Також неможливо змішувати біти арифметики DIY з бітовими полями, наприклад, зробити маску, яка одночасно перевіряє декілька бітів. Ви, звичайно, можете використовувати && і сподіваємося, що компілятор буде правильно його оптимізувати ... - R..
Бітові поля погано в багатьох відношеннях, я міг би майже написати книгу про це. Справді, мені було мало що зробити для трохи польової програми, яка потребує відповідності MISRA-C. MISRA-C впроваджує всі зафіксовані поведінку документальні документи, тому я закінчив писати досить есе про все, що може стати не так у бітних полях. Бітовий порядок, endianess, бісткі підбивки, байтів підбивки, різні інші проблеми вирівнювання, неявні та явні перетворення типів у бітове поле, і UB, якщо int не використовується і так далі. Замість цього використовуйте bitwise-оператори для менших помилок та переносного коду. Бітові поля повністю зайві. - Lundin
Як і більшість функцій мови, бітні поля можуть бути використані правильно або їх можна зловживати. Якщо вам потрібно упакувати кілька малих значень в єдину int, бітні поля можуть бути дуже корисними. З іншого боку, якщо ви почнете робити припущення про те, як бітові поля вказуються на дійсний вміст, ви просто задаєте проблеми. - Ferruccio
@endolith: Це було б непогано. Ви могли б зробити це роботою, але це не обов'язково буде переноситись на інший процесор або в інший компілятор або навіть на наступний випуск того ж компілятора. - Ferruccio
@ R Можна використовувати обидва struct може бути поміщений всередині (зазвичай анонімний) union з цілим числом і т. д. Це працює. (Я усвідомлюю, що це стара річ) - Shade


Я використовую макроси, визначені в файлі заголовка для обробки встановлених біт і очищення:

/* a=target variable, b=bit number to act upon 0-n */
#define BIT_SET(a,b) ((a) |= (1ULL<<(b)))
#define BIT_CLEAR(a,b) ((a) &= ~(1ULL<<(b)))
#define BIT_FLIP(a,b) ((a) ^= (1ULL<<(b)))
#define BIT_CHECK(a,b) ((a) & (1ULL<<(b)))

/* x=target variable, y=mask */
#define BITMASK_SET(x,y) ((x) |= (y))
#define BITMASK_CLEAR(x,y) ((x) &= (~(y)))
#define BITMASK_FLIP(x,y) ((x) ^= (y))
#define BITMASK_CHECK_ALL(x,y) (((x) & (y)) == (y))   // warning: evaluates y twice
#define BITMASK_CHECK_ANY(x,y) ((x) & (y))

125
2017-09-08 21:07



Я розумію, що це 5-річний пост, але в жоден з цих макросів немає ніяких аргументів, Dan - Robert Kelly
BITMASK_CHECK(x,y) ((x) & (y)) повинно бути ((x) & (y)) == (y) в іншому випадку він повертає неправильний результат на мультибіску (напр. 5 проти 3) / * Привіт усім монгольгам:) * / - brigadir
1 має бути (uintmax_t)1 або подібний, якщо хтось намагається використовувати ці макроси на long або більший тип - M.M
Or 1ULL працює так само, як і (uintmax_t) на більшості реалізацій. - Peter Cordes
@brigadir: залежить від того, чи хочете ви перевірити встановлений біт або всі біти. Я оновив відповідь, щоб включити обидва з описовими іменами. - Peter Cordes


Іноді варто використовувати enum до ім'я біти:

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

Тоді використовуйте імена в подальшому. І.е. писати

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

встановити, очистити і перевірити. Таким чином ви сховаєте магічні цифри з решти коду.

Крім того, я схвалюю рішення Джеремі.


99
2017-09-17 02:04



З іншого боку, ви могли б зробити clearbits() функція замість &= ~. Чому ви використовуєте перелік для цього? Я думав, що вони призначені для створення безлічі унікальних змінних з прихованою довільною цінністю, але ви призначаєте певне значення кожному. Отже, яка користь, а не просто визначити їх як змінні? - endolith
@endolith: Використання enums для наборів пов'язаних констант висувається довгий шлях в програмуванні c. Я підозрюю, що з сучасними компіляторами єдина перевага над const short або все інше, що вони явно згруповані разом. І коли ти їх хочеш за щось інший ніж бітові маски ви отримуєте автоматичну нумерацію. Звичайно, в с ++ вони також утворюють різні типи, які дають вам додаткові статистичні перевірки помилок. - dmckee
Ви потрапляєте в невизначені константи переліку, якщо ви не визначите константи для кожної з можливих значень бітів. Що таке? enum ThingFlags вартість для ThingError|ThingFlag1, наприклад? - Luis Colorado
Якщо ви використовуєте цей метод, майте на увазі, що константи enum завжди мають підписаний тип int. Це може викликати будь-які тонкі помилки через неявне просування цілого числа або побітові операції на підписані типи. thingstate = ThingFlag1 >> 1 буде, наприклад, викликати поведінку, визначену для реалізації. thingstate = (ThingFlag1 >> x) << y може викликати невизначену поведінку. І так далі. Щоб бути в безпеці, завжди звертайтеся до непідписаного типу. - Lundin
@Lundin: починаючи з C ++ 11, ви можете встановити основний тип переліку, наприклад: enum My16Bits: unsigned short { ... }; - Aiken Drum


Від snip-c.zip'S bitops.h:

/*
**  Bit set, clear, and test operations
**
**  public domain snippet by Bob Stout
*/

typedef enum {ERROR = -1, FALSE, TRUE} LOGICAL;

#define BOOL(x) (!(!(x)))

#define BitSet(arg,posn) ((arg) | (1L << (posn)))
#define BitClr(arg,posn) ((arg) & ~(1L << (posn)))
#define BitTst(arg,posn) BOOL((arg) & (1L << (posn)))
#define BitFlp(arg,posn) ((arg) ^ (1L << (posn)))

ОК, давайте аналізуємо речі ...

Загальний вираз, який ви, здається, має проблеми в усіх з них, є "(1L << (posn))". Все це - створити маску з одним бітком і який буде працювати з будь-яким цілим типом. Аргумент "posn" вказує Позиція, де ви хочете трохи. Якщо posn == 0, то цей вираз буде оцінити до:

    0000 0000 0000 0000 0000 0000 0000 0001 binary.

Якщо posn == 8, це буде оцінювати до

    0000 0000 0000 0000 0000 0001 0000 0000 binary.

Інакше кажучи, він просто створює поле 0 з 1 за вказаним позиція Єдина складна частина полягає в макросі BitClr (), де нам потрібно встановити один 0 біт у полі 1-го. Це досягається за допомогою 1-го доповнення того ж виразу, що позначається оператором tilde (~).

Як тільки маска створена, вона застосовується до аргументу так само, як ви пропонуєте. за допомогою побітових і (&), або (|) і xor (^) операторів. Оскільки маска має довгий тип, макроси працюватимуть так само добре, як на символах, коротких, int, або довго.

Суть в тому, що це загальне рішення для цілого класу проблеми Звичайно, це можливо і навіть доречно переписати еквівалент будь-якого з цих макросів із явними значеннями маски щоразу, коли ви потрібна одна, а чому це зробити? Пам'ятайте, що макрозаміщення відбувається в препроцесор і тому сформований код відображатиме той факт, що значення компілятором вважаються постійними - тобто він настільки ж ефективний для використання узагальнені макроси, щоб "винайти колесо" кожен раз, коли вам потрібно бітна маніпуляція.

Невпевнений? Ось декілька тестових кодів - я використав Watcom C з повною оптимізацією і без використання _cdecl, так що отримана розбірка буде такою ж чистою, як можливо:

---- [TEST.C] ----------------------------------------- -----------------------

#define BOOL(x) (!(!(x)))

#define BitSet(arg,posn) ((arg) | (1L << (posn)))
#define BitClr(arg,posn) ((arg) & ~(1L << (posn)))
#define BitTst(arg,posn) BOOL((arg) & (1L << (posn)))
#define BitFlp(arg,posn) ((arg) ^ (1L << (posn)))

int bitmanip(int word)
{
      word = BitSet(word, 2);
      word = BitSet(word, 7);
      word = BitClr(word, 3);
      word = BitFlp(word, 9);
      return word;
}

---- [TEST.OUT (розбирається)] -------------------------------------- ---------

Module: C:\BINK\tst.c
Group: 'DGROUP' CONST,CONST2,_DATA,_BSS

Segment: _TEXT  BYTE   00000008 bytes  
 0000  0c 84             bitmanip_       or      al,84H    ; set bits 2 and 7
 0002  80 f4 02                          xor     ah,02H    ; flip bit 9 of EAX (bit 1 of AH)
 0005  24 f7                             and     al,0f7H
 0007  c3                                ret     

No disassembly errors

---- [закінчення] ------------------------------------------ ----------------------


34
2018-06-05 14:18



2 речі про це: (1) переглядаючи ваші макроси, деякі можуть неправильно вважати, що макроси насправді встановлюють / очищують / перевертають біти в arg, однак немає призначення; (2) ваш тест.c не є повним; Я підозрюю, якщо у вас є більше випадків, коли ви знайдете проблему (читацька вправа) - Dan
-1 Це просто дивна обфускація. Ніколи не повторно не винаходити мову С, приховуючи мовний синтаксис поза макросами дуже погана практика. Тоді деякі дивацтва: по-перше, 1L підписаний, тобто всі операції біт будуть виконуватися за підписаним типом. Все, що перейшло до цих макросів, повернеться, як підписано довго. Не добре. По-друге, це буде працювати дуже неефективно на малих центральних процесорах, оскільки він забезпечує довгий час виконання операцій на рівні int. По-третє, функціонально подібні макроси є основою всього зла: у вас немає типової безпеки взагалі. Також, попередній коментар про призначення не дуже правильний. - Lundin
Це не вийде, якщо arg є long long. 1L повинен бути максимально можливим, тому (uintmax_t)1 . (Ви можете піти з 1ull) - M.M
Чи оптимізували ви для розміру коду? На основних процесорних процесорах Intel ви отримаєте часткові реєстраційні лавки при читанні AX або EAX після повернення цієї функції, оскільки він записує 8-бітні компоненти EAX. (Це добре для процесорів AMD або інших, які не перейменовують часткові регістри окремо від повного реєстру. Haswell / Skylake не перейменувати AL окремо, але вони перейменовують AH.) - Peter Cordes


Для початківця я хотів би пояснити трохи більше з прикладом:

Приклад:

value is 0x55;
bitnum : 3rd.

The & оператор використовується перевірити біт:

0101 0101
&
0000 1000
___________
0000 0000 (mean 0: False). It will work fine if the third bit is 1 (then the answer will be True)

Переключити або перевернути:

0101 0101
^
0000 1000
___________
0101 1101 (Flip the third bit without affecting other bits)

| оператор: встановіть біт

0101 0101
|
0000 1000
___________
0101 1101 (set the third bit without affecting other bits)

29
2017-09-07 00:45





Використовуйте побітові оператори: &  | 

Щоб встановити останній біт в 000b:

foo = foo | 001b

Щоб перевірити останній біт в foo:

if ( foo & 001b ) ....

Щоб очистити останній біт в foo:

foo = foo & 110b

я використав XXXb для ясності Ви, ймовірно, будете працювати з представленням HEX, залежно від структури даних, в якій ви вставляєте біти.


26
2017-07-13 06:53



У бінарному значенні немає двозначних позначень. Константи цілих двомісних є нестандартним розширенням. - Lundin


Ось мій улюблений бітовий арифметичний макрос, який працює для будь-якого типу беззнакового цілого масиву з 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, &)) ...

тощо.


24
2018-06-14 15:23



Це добре прочитати, але слід пам'ятати про можливі побічні ефекти. Використовуючи BITOP(array, bit++, |=); в циклі, швидше за все, не зробить того, що бажає абонент. - foraidt
Дійсно =) Одним із варіантів, який ви можете віддати перевагу, є розділити його на 2 макроси, 1 - для адресації елемента масиву, а інший - для переміщення біта на місце, ала BITCELL(a,b) |= BITMASK(a,b); (обидва беруть a як аргумент для визначення розміру, але останній ніколи не оцінить a оскільки він з'являється тільки в Росії sizeof) - R..
@ R .. Ця відповідь дійсно стара, але я, напевно, вважаю за краще функцію макросу в цьому випадку. - PC Luddite
Малий: 3-й (size_t) Залишається, як правило, там, лише щоб застрахувати деяких непідписана математика з %. Міг (unsigned) там - chux
The (size_t)(b)/(8*sizeof *(a)) необов'язково може звузитись b перед поділом Лише проблема з дуже великими бітними масивами. Ще цікавий макрос. - chux