C, PHP, VB, .NET

Дневникът на Филип Петров


* Побитови операции

Публикувано на 24 октомври 2008 в раздел С/С++.

Езикът С притежава част от качествата на асемблерните езици. Той разполага с пълен набор от операции за работа с отделни битове на числените стойности - поразредни операции. Тези операции позволяват проверяване, установяване или преместване на отделни битове на променливи от тип int или char. Поразредните операции се използват много често при писането на драйвери за устройства.

Всеки обект се разполага като двоично число в паметта. Определен брой байтове, в зависимост от конкретния компютър, определят "машинна дума".

Поразредните операции се означават със следните символи:

1. & - поразредно логическо И:

	1 & 1 = 1
	0 & 0 = 0
	0 & 1 = 0
	1 & 0 = 0

	Пример:
	1 0 0 1 0
	&
	1 0 1 1 0
	---------
	1 0 0 1 0

Изолзува се обикновено за нулиране на отделни битове в числената стойност на резултата. Ако някой бит в единия или другия операнд има нулева стойност, съответния по позиция бит в резултата също ще има нулева стойност.

2. | - поразредно логическо ИЛИ

	1 | 1 = 1
	1 | 0 = 1
	0 | 1 = 1
	0 | 0 = 0

	Пример:
	1 0 0 1 0 1
	|
	0 1 0 1 1 0
	-----------
	1 1 0 1 1 1

Можем да разгледаме операцията като обратна на миналата - можем да направим отделни битове единици в резултата.

3. ^ - поразредно логическо ИЗКЛЮЧВАЩО ИЛИ (XOR)

	1 ^ 1 = 0
	1 ^ 0 = 1
	0 ^ 1 = 1
	0 ^ 0 = 0

	Пример:
	1 0 0 1 0
	^
	1 1 0 0 1
	---------
	0 1 0 1 1

Определени битове в резултата се установяват като единица само когато съответните битове в операндите са различни.

4. ~ - поразредно логическо ДОПЪЛВАНЕ ДО 1
Това вече е едноместна операция с асоциативно правило на изпълнение отдясно наляво. Операнд може да бъде всеки валиден израз, имащ резултат цяла стойност. При изпълнението на операцията всеки бит на операнда се променя с обратната си стойност, т.е. 0 става 1, а 1 става 0. От това веднага следва, че двукратното изпълнение на операцията възстановява числото в първоначален вид.

	Пример:
	~11010101
	---------
	 00101010

5. >> - изместване вдясно
Това е двуоперандна операция. Първият операнд е валиден израз връщащ число, а вторият и брой битове, с които отместваме вдясно.

	Пример:
	01111000
	>> 3
	--------
	00001111

Ефектът от примера е, че все едно три пъти сме разделили числото на две. Например 120 >> 2 ще върне резултат 30 ((120/2)/2).

6. << - изместване вляво
Обратната операция на изместването вдясно.

	Пример:
	00001111
	<< 3
	--------
	01111000

Ефектът също е обратния - все едно сме умножили числото три пъти по две. Например 15 << 3 ще върне резултат 120 (15*2*2*2).

При операциите изместване вляво или вдясно трябва да знаете, че изместените битове се губят. Следният пример го демонстрира:

	00001111
	>> 1
	--------
	00000111
	<< 1
	--------
	00001110

Затова резултатът от операциите е неопределен, ако броя битове е по-голям или равен на дължината на първия операнд.

 



8 коментара


  1. Много полезно като метод и служи перфектно за ускоряване на процеса на работа на програмите.
    Но доколкото знам малко хора го учат като метод в университетите.

  2. Точно защото се учи "отгоре-отгоре" сега ми трябва за една задача. Някой ако може да помага. Трябва да разменя стойностите на 2 променливи(които си задаваме) побитово без използването на 3-та променлива. плс пишете тук или на скайп: tzanev8989

  3. Ето няколко варианта:

    1: Чрез събиране и изваждане
    a=a+b;
    b=a-b;
    a=a-b;

    2: Чрез умножение и деление
    a=a*b;
    b=a/b;
    a=a/b;

    3: Чрез XOR (т.е. побитово)
    x = x^y
    y = x^y
    x = x^y

  4. забравих да кажа ако може да е Java Код, но и C++ става

  5. Странно, но при мен при "побитовото изместване" не изчезват битове. Блогът е супер и има супер много полезна информация! Ще има четене!

  6. Като ме върнахте на темата - ето нещо, което ми се наложи да пиша наскоро:

    Често се използват при дефинирането на "флагове" (т.е. комбинация от опции, които в края на краищата искаме да видим дали са включени или не) - вместо огромно количество if-else или switch оператори, ние можем лесно да се ориентираме ако използваме побитови оператори, например:

    final int op1 = 1; // 0001
    final int op2 = 2; // 0010
    final int op3 = 4; // 0100
    final int op4 = 8; // 1000
    ... // други, степени на двойката
    int settings = 0; // първоначално всичко изключено

    Ако някой флаг бъде включен - просто добавяме неговата стойност към settings. Така съответния пореден бит за този флаг става 1. Обратно - при изключването изваждаме съответния флаг и бита му става 0. Така с една променлива изключително лесно виждаме кои флагове са включени и кои не накуп. Например:

    settings |= op4; // включва op4
    settings &= ~op3; // изключва op3
    if((flags & (op3 | op4 )) == (op3 | op4)) {...} // проверява дали op3 и op4 са включени

    Така извършени операциите са много бързи.

    Същото може да се използва за означение на RGB цветове:

    final int red_mask = 0x000000FF
    final int green_mask = 0x0000FF00
    final int blue_mask = 0x00FF0000

    int pixel = 0x...; // форматът на цветовете е RRGGBB и обикновено се записват в HEX от 00 до FF (0,...,255)
    int red = (pixel & red_mask); // извлича червеното от пиксела
    int green = (pixel & green_mask) >> 8; // зеленото
    int blue = (pixel & blue_mask) >> 16; // синьото

    Eто как може да се комбинират цветовете обратно (примерно след като сигналите са изпратени до съответното устройство):
    int vazstanovenPixel = (red) | (green << 8) | (blue << 16); Също така се използват при правенето на сокети и други мрежови връзки или връзки с компютърна периферия. Там винаги има "стоп битове", "контролни суми", и др., които обикновено се осъществяват чрез побитови операции. При кодирането и компресията на файлове се използват много побитови операции. Зад много хардуерни устройства, като например програматори за перални, хладилници и т.н., стои "елементарен софтуер", който обикновено се крепи на комбинации от побитови оператори (нещо подобно на примера с флаговете, но може и да е по-сложно). XOR оператора се използва в по-старите графични среди или съвременните като remote desktop (нуждаещи се от малък трафик). Причината е, че като се направи два пъти XOR се връща оригиналното число, т.е. няма нужда от "redraw" при извършването на определени операции (пр. оцветяването при селекция с мишка). Ето например и как може да се използват като много бърза (не добра, но в елементарни случаи върши работа) hash функция: int a = 4328754; int b = 1232145; int c = 1231231; int hash = a ^ b ^ c; По-сложните hash функции също използват побитови операции. Причината - бързина. Всичко писано на асемблер ще има нужда от побитови операции. Т.е. всички embedded системи например ги използват. Base64 кодирането ги използва - то превръща бинарна информация в символи (например се използва при трансфер на e-mail). Дотолкова съм чувал - за повече - Google :) Със сигурност четенето и записването на файлове (IO) използва побитови операции. Чувал си за "subnet" при IP адресите? Е, те се възползват именно от побитовите операции. Ето пример: http://vmrejata.info/tcpip/312-vuvedeniesubnetmasks.html

    Ето две други бързи връзки от Google с примери:

    http://onjava.com/pub/a/onjava/2005/02/02/bitsets.html

    http://www.devarticles.com/c/a/Cplusplus/Bitwise-Operators-in-Action/

Добави коментар

Адресът на електронната поща няма да се публикува


*