Pytanie Jak ustawić, wyczyścić i przełączyć jeden bit?


Jak ustawić, wyczyścić i zmienić nieco w C / C ++?


2053
2017-09-07 00:42


pochodzenie


Przeczytaj to: graphics.stanford.edu/~seander/bithacks.html i kiedy to opanujesz, przeczytaj ten: realtimecollisiondetection.net/blog/?p=78 - ugasoft
Możesz być również zainteresowany wyjazdem Bit Twiddler, Bit Twiddling Hacks, i Aggregate Magic Algorithms.
Ten link pomógł mi zrozumieć, jak te operacje rzeczywiście działają - cs.umd.edu/class/sum2003/cmsc311/Notes/BitOp/setBitI.html Tutaj znajdziesz więcej interesujących operacji - cs.umd.edu/class/sum2003/cmsc311/Notes - rajya vardhan
Mogę sobie łatwo wyobrazić, że nie chodzi o samo pytanie, ale o stworzenie bardzo przydatnego przewodnika. Biorąc pod uwagę, że dostałem się tutaj, kiedy potrzebowałem trochę informacji. - Joey van Hummel
@glglgl / Jonathon ma wystarczająco dużo znaczenia, aby C ++ zostało oznaczone jako takie. To historyczne pytanie z dużym ruchem, a tag C ++ pomoże innym zainteresowanym programistom znaleźć je za pomocą wyszukiwarki Google. - Luchian Grigore


Odpowiedzi:


Ustawienie nieco

Użyj operatora bitowego OR (|), aby ustawić nieco.

number |= 1UL << n;

To ustawi nth bit of number.

Posługiwać się 1ULL gdyby number jest szerszy niż unsigned long; promocja 1UL << n nie nastąpi, dopóki nie ocenisz 1UL << n gdzie nieokreślone zachowanie przesuwa się o więcej niż szerokość a long. To samo dotyczy wszystkich pozostałych przykładów.

Czyszczenie trochę

Użyj operatora bitowego AND (&), aby trochę wyczyścić.

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

To usunie nth bit of number. Musisz odwrócić ciąg bitów za pomocą operatora bitowego NOT (~), następnie ORAZ.

Przełączam trochę

Operator XOR (^) można użyć do przełączania się.

number ^= 1UL << n;

To przełączy się na nth bit of number.

Sprawdzanie trochę

Nie prosiłeś o to, ale równie dobrze mógłbym to dodać.

Aby sprawdzić bit, przesuń liczbę n w prawo, następnie bitowo ORAZ:

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

To doda wartość nth bit of number do zmiennej bit.

Zmienianie nth bit to x

Ustawianie nth bit do któregokolwiek z nich 1 lub 0 można osiągnąć przy pomocy C ++ w uzupełnieniu do 2:

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

Kawałek n zostanie ustawiony, jeśli x jest 1i wyczyszczone, jeśli x jest 0. Gdyby x ma jakąś inną wartość, dostajesz śmieci. x = !!x będzie booleanize to do 0 lub 1.

Aby było to niezależne od zachowania 2 negacji uzupełnienia (gdzie -1 ma ustawione wszystkie bity, w przeciwieństwie do implementacji C ++ w postaci znaku C ++ lub znaku / magii), użyj unsigned negation.

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

lub

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

Zasadniczo dobrym pomysłem jest użycie niepodpisanych typów do przenośnej manipulacji bitem.

Dobrym pomysłem jest również ogólne kopiowanie i wklejanie kodu, dlatego wiele osób używa makr preprocesora (np wiki społeczności odpowiedzą dalej) lub jakiegoś rodzaju enkapsulacji.


3003
2017-09-07 00:50



Chciałbym zauważyć, że na platformach, które mają natywne wsparcie dla bit set / clear (np. Mikrokontrolery AVR), kompilatory często tłumaczą "mójByte | = (1 << x)" do instrukcji natywnego ustawiania / usuwania bitów, gdy x jest stała, np: (1 << 5) lub const unsigned x = 5. - Aaron
bit = liczba & (1 << x); nie wstawi wartości bitu x do bitu, chyba że bit ma typ _Bool (<stdbool.h>). W przeciwnym razie bit = !! (liczba & (1 << x)); będzie.. - Chris
dlaczego nie zmienisz ostatniego bit = (number >> x) & 1 - aaronman
1 to jest int literał, który jest podpisany. Tak więc wszystkie operacje tutaj działają na liczbach podpisanych, które nie są dobrze określone przez normy. Standardy nie gwarantują dwójki uzupełnień ani przesunięć arytmetycznych, więc lepiej jest ich używać 1U. - Siyuan Ren
wolę number = number & ~(1 << n) | (x << n); for Zmienianie n-tego bitu na x. - Eliko


Korzystanie ze standardowej biblioteki C ++: std::bitset<N>.

Albo Podnieść wersja: boost::dynamic_bitset.

Nie ma potrzeby rozwijania własnych:

#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

Wersja Boost umożliwia bitset w czasie wykonywania w porównaniu z standardowa biblioteka bitset w czasie kompilacji.


383
2017-09-18 00:34



+1. Nie, że std :: bitset jest użyteczny z "C", ale ponieważ autor oznaczył swoje pytanie słowem "C ++", AFAIK, twoja odpowiedź jest najlepsza tutaj ... std :: vector <bool> to inny sposób, jeśli ktoś zna jego zalety i wady - paercebal
@andrewdotnich: wektor <bool> jest (niestety) specjalizacją przechowującą wartości jako bity. Widzieć gotw.ca/publications/mill09.htm po więcej informacji... - Niklas
Może nikt o tym nie wspomniał, ponieważ został oznaczony jako osadzony. W większości systemów wbudowanych unikasz STL jak ognia. A wsparcie dla wsparcia jest prawdopodobnie bardzo rzadkim ptakiem, który można zauważyć wśród większości wbudowanych kompilatorów. - Lundin
@Martin Jest to bardzo prawdziwe. Poza określonymi zabójcami wydajności, takimi jak STL i szablony, wiele systemów wbudowanych całkowicie unika całkowicie całych standardowych bibliotek, ponieważ są one tak trudne do zweryfikowania. Większość osadzonych gałęzi obejmuje takie standardy jak MISRA, które wymagają statycznych narzędzi do analizy kodu (każdy profesjonalista oprogramowania powinien używać takich narzędzi, a nie tylko osób osadzonych). Ogólnie rzecz biorąc, ludzie mają lepsze rzeczy do roboty niż prowadzenie analizy statycznej przez całą standardową bibliotekę - jeśli jej kod źródłowy jest nawet dostępny dla nich w konkretnym kompilatorze. - Lundin
@Lundin: Twoje wypowiedzi są zbyt szerokie (w związku z tym nie ma sensu się o nie kłócić). Jestem pewien, że potrafię znaleźć sytuacje, w których są prawdziwe. To nie zmienia mojego początkowego punktu. Obie te klasy są idealnie w porządku do użytku w systemach wbudowanych (i wiem, że są one używane). Twój początkowy punkt dotyczący STL / Boost, który nie jest używany w systemach wbudowanych, jest również błędny. Jestem pewien, że są systemy, które ich nie używają, a nawet systemy, które ich używają, są używane rozsądnie, ale mówiąc, że nie są używane, są po prostu niewłaściwe (ponieważ są systemy, w których są używane). - Martin York


Inną opcją jest użycie pól bitowych:

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

struct bits mybits;

definiuje 3-bitowe pole (właściwie to trzy 1-bitowe feldy). Operacje bitowe stają się teraz nieco (haha) prostsze:

Aby ustawić lub wyczyścić bit:

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

Aby przełączyć się nieco:

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

Sprawdzanie trochę:

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

Działa to tylko w przypadku pól bitowych o stałym rozmiarze. W przeciwnym razie musisz uciekać się do technik bit-twiddling opisanych w poprzednich postach.


213
2017-09-11 00:56



Zawsze uważałem, że używanie bitfieldów to zły pomysł. Nie masz kontroli nad kolejnością przydzielania bitów (od góry lub od dołu), co uniemożliwia serializację wartości w sposób stabilny / przenośny z wyjątkiem bit-at-a-time. Niemożliwe jest również połączenie arytmetyki bitów DIY z bitfieldami, na przykład tworzenie maski, która testuje kilka bitów naraz. Możesz oczywiście użyć && i mieć nadzieję, że kompilator zoptymalizuje ją poprawnie ... - R..
Pola bitowe są złe na tak wiele sposobów, że prawie mogę napisać o tym książkę. Prawdę mówiąc, prawie musiałem to zrobić w przypadku niewielkiego programu terenowego, który wymagał zgodności z MISRA-C. MISRA-C wymusza udokumentowanie wszystkich zachowań definiowanych przez implementację, dlatego napisałem dość esej o wszystkim, co może pójść źle w polach bitowych. Kolejność bitów, endians, bity dopełniające, bajty dopełnienia, różne inne problemy z wyrównaniem, konwersje typu niejawnego i jawnego do pola bitowego i od niego, UB, jeśli int nie jest używane i tak dalej. Zamiast tego użyj operatorów bitowych dla mniej błędów i przenośnego kodu. Pola bitowe są całkowicie zbędne. - Lundin
Podobnie jak większość funkcji językowych, pola bitowe mogą być używane poprawnie lub mogą być nadużywane. Jeśli potrzebujesz spakować kilka małych wartości do pojedynczej int, pola bitowe mogą być bardzo użyteczne. Z drugiej strony, jeśli zaczniesz przyjmować założenia o tym, jak pola bitowe są odwzorowane na rzeczywiste zawierające int, po prostu prosisz o kłopoty. - Ferruccio
@endolith: To nie byłby dobry pomysł. Możesz sprawić, żeby to działało, ale niekoniecznie byłoby przenośne dla innego procesora, albo innego kompilatora, albo nawet dla następnej wersji tego samego kompilatora. - Ferruccio
@R. Możliwe jest użycie obu, struct można umieścić w (zwykle anonimowym) union z liczbą całkowitą itd. Działa. (Rozumiem, że jest to stary wątek btw) - Shade


Używam makr zdefiniowanych w pliku nagłówkowym do obsługi ustawień bitowych i czyszczenia:

/* 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



Uh, zdaję sobie sprawę, że jest to pięcioletni post, ale w żadnym z tych makr nie ma duplikacji argumentów, Dan - Robert Kelly
BITMASK_CHECK(x,y) ((x) & (y)) musi być ((x) & (y)) == (y) w przeciwnym razie zwraca nieprawidłowy wynik na masce multibit (np. 5 vs. 3) / * Witam wszystkich grabarzy:) * / - brigadir
1 powinno być (uintmax_t)1 lub podobne, na wypadek gdyby ktokolwiek próbował użyć tych makr na long lub większy typ - M.M
Lub 1ULL działa równie dobrze jak (uintmax_t) na większości wdrożeń. - Peter Cordes
@brigadir: zależy od tego, czy chcesz sprawdzić zestaw bitów, czy wszystkie ustawione bity. Zaktualizowałem odpowiedź, aby zawierała zarówno opisowe nazwy. - Peter Cordes


Czasami warto skorzystać z enum do Nazwa bity:

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

Następnie użyj nazwy później. To znaczy. pisać

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

ustawić, wyczyścić i przetestować. W ten sposób ukrywasz magiczne cyfry przed resztą kodu.

Poza tym popieram rozwiązanie Jeremy'ego.


99
2017-09-17 02:04



Alternatywnie możesz zrobić clearbits() funkcja zamiast &= ~. Dlaczego używasz do tego wyliczenia? Sądziłem, że chodziło o stworzenie mnóstwa unikatowych zmiennych z ukrytą dowolną wartością, ale przypisujesz konkretną wartość każdemu. Więc jakie są korzyści, a nie tylko definiowanie ich jako zmiennych? - endolith
@endolith: Zastosowanie enums dla zestawów powiązanych stałych wraca daleko w programowaniu c. Podejrzewam, że dzięki nowoczesnym kompilatorom jedyna przewaga nad const short czy cokolwiek to jest, że są one wyraźnie zgrupowane razem. A kiedy chcesz je za coś inny niż maski bitowe otrzymujesz automatyczną numerację. W C ++ oczywiście tworzą one również różne typy, co daje ci trochę statystycznych błędów sprawdzania błędów. - dmckee
Dostaniesz się do niezdefiniowanych stałych enum, jeśli nie określisz stałej dla każdej z możliwych wartości bitów. Co to jest enum ThingFlags wartość dla ThingError|ThingFlag1, na przykład? - Luis Colorado
Jeśli używasz tej metody, pamiętaj, że stałe wyliczeniowe są zawsze typu podpisanego int. Może to powodować wszelkiego rodzaju subtelne błędy z powodu niejawnej promocji liczb całkowitych lub operacji bitowych na typach podpisanych. thingstate = ThingFlag1 >> 1na przykład wywoła zachowanie zdefiniowane przez implementację. thingstate = (ThingFlag1 >> x) << y może wywoływać niezdefiniowane zachowanie. I tak dalej. Aby być bezpiecznym, zawsze rzucaj do typu bez znaku. - Lundin
@Lundin: od C ++ 11 można ustawić podstawowy typ wyliczenia, np .: enum My16Bits: unsigned short { ... }; - Aiken Drum


Od snip-c.zipBitops.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)))

OK, przeanalizujmy rzeczy ...

Wspólnym wyrażeniem, które wydaje się mieć problemy we wszystkich z nich jest "(1L << (posn))". Wszystko to tworzy maskę z pojedynczym bitem i który będzie działał z dowolnym typem całkowitym. Argument "posn" określa pozycja, w której chcesz bit. Jeśli posn == 0, to wyrażenie będzie ocenić na:

    0000 0000 0000 0000 0000 0000 0000 0001 binary.

Jeśli posn == 8, oceni na

    0000 0000 0000 0000 0000 0001 0000 0000 binary.

Innymi słowy, po prostu tworzy pole 0 z 1 w podanym pozycja. Jedyną trudną częścią jest makro BitClr (), w którym musimy ustawić pojedynczy 0 bit w polu 1. Osiąga się to za pomocą 1-ek uzupełnienie tego samego wyrażenia, co oznaczono przez operatora tyldy (~).

Po utworzeniu maski jest ona stosowana do argumentu tak, jak sugerujesz, za pomocą operatorów bitowych i (&) lub (|) i xor (^). Od maski jest typu long, makra będą działać równie dobrze na char, short, int, lub długie.

Najważniejsze jest to, że jest to ogólne rozwiązanie dla całej klasy problemy. Oczywiście, możliwe jest nawet odpowiednie przepisanie odpowiednik dowolnego z tych makr z jawnymi wartościami maski za każdym razem potrzebować, ale dlaczego? Pamiętaj, że podstawienie makra występuje w preprocesor i tak wygenerowany kod będzie odzwierciedlał fakt, że wartości są uważane za stałe przez kompilator - tzn. są równie wydajne w użyciu uogólnione makra, które "wymyślają koło" za każdym razem, gdy musisz to zrobić manipulacja bitami.

Nieprzekonany? Oto kod testowy - użyłem Watcom C z pełną optymalizacją i bez użycia _cdecl, więc wynikowy demontaż będzie tak czysty jak możliwy:

---- [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 (zdemontowany)] -------------------------------------- ---------

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

---- [finis] ------------------------------------------- ----------------------


34
2018-06-05 14:18



2 rzeczy na ten temat: (1) podczas przeglądania twoich makr, niektórzy mogą błędnie sądzić, że makra faktycznie ustawiają / usuwają / odwracają bity w arg, jednak nie ma przydziału; (2) twoje test.c nie jest kompletne; Podejrzewam, że jeśli masz więcej przypadków, możesz znaleźć problem (ćwiczenie czytnika) - Dan
-1 To jest po prostu dziwna obfuskacja. Nigdy nie wynajduj ponownie języka C przez ukrywanie składni języka za makrami bardzo zła praktyka. Następnie niektóre osobliwości: pierwsza, 1L jest podpisana, co oznacza, że ​​wszystkie operacje bitowe będą wykonywane na podpisanym typie. Wszystko przekazane do tych makr zostanie zwrócone jako podpisane długo. Niedobrze. Po drugie, będzie działać bardzo nieefektywnie na mniejszych procesorach, ponieważ wymusza długie działanie, gdy operacje mogły być na poziomie int. Po trzecie, makra funkcyjne są źródłem wszelkiego zła: nie masz żadnego rodzaju bezpieczeństwa. Również poprzedni komentarz o braku przypisania jest bardzo ważny. - Lundin
To się nie powiedzie, jeśli arg jest long long. 1L musi być możliwie najszerszym typem, więc (uintmax_t)1 . (Możesz uciec 1ull) - M.M
Czy zoptymalizowałeś dla rozmiaru kodu? W procesorach głównych Intela otrzymasz stray z częściowym rejestrem podczas odczytu AX lub EAX po powrocie tej funkcji, ponieważ zapisuje 8-bitowe komponenty EAX. (Jest to w porządku na procesorach AMD lub innych, które nie zmieniają nazw rejestrów częściowych oddzielnie od pełnego rejestru. Haswell / Skylake nie zmieniają nazwy AL oddzielnie, ale zmieniają nazwę AH.). - Peter Cordes


Dla początkujących chciałbym wyjaśnić nieco więcej na przykładzie:

Przykład:

value is 0x55;
bitnum : 3rd.

The & operator jest używany sprawdź bit:

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)

Przełącz lub odwróć:

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

| operator: ustaw bit

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

29
2017-09-07 00:45