Язык Си. Битовые операторы и операции. Трюки с битами.

Язык Си. Битовые операторы и операции.

Побитовые операции часть 1.

Побитовые операции часть 2.

Задача - манипуляция с битами, постановка задачи

Решение задачи - шифровка PIN кода.

Битовые операторы - 

~     - побитовое отрицание

&    - побитовое И

|      - побитовое ИЛИ

^    - исключающее ИЛИ

>>  - побитовый сдвиг вправо

<<  - побитовый сдвиг влево

Побитовые операции применяются только к целочисленным типам данных.

~     - побитовое отрицание

Можно назвать инверсией, если бит установлен в 0 он устанавливается в 1 и наоборот, если установлен в 1 после операции устанавливается в 0.

void print_bit_byte(unsigned char aByte)
{
  printf("%c", (0b10000000 & aByte) ? '1' : '0');
  printf("%c", (0b01000000 & aByte) ? '1' : '0');
  printf("%c", (0b00100000 & aByte) ? '1' : '0');
  printf("%c", (0b00010000 & aByte) ? '1' : '0');
  printf("%c", (0b00001000 & aByte) ? '1' : '0');
  printf("%c", (0b00000100 & aByte) ? '1' : '0');
  printf("%c", (0b00000010 & aByte) ? '1' : '0');
  printf("%c", (0b00000001 & aByte) ? '1' : '0');
  printf("\n");
}

int main()
{
  unsigned char uc = 0b00111100;
  print_bit_byte(uc);
  print_bit_byte(~uc);
  return 0;
}

Если тип данных к которому применяется эта операция является беззнаковым, то результирующим типом является знаковый.
К примеру чтобы получить из числа x отрицательное значение, не используя оператор
(-x) нужно сделать так: ~(x - 1)

  char ch = ~(60 - 1);
  if(ch == -60)
    printf("OK\n");

  ch = ~(1 - 1);
  if(ch == -1)
    printf("OK\n");

&     - побитовое И
Можно назвать умножением(для простоты запоминания), соответственно - 0 умножить на 0 будет 0, 1 умножить на 0 будет 0, 1 умножить на 1 будет 1.
    0101
& 
    0011
=
    0001  
С помощью этой операции, можно проверять состояние отдельных битов, для этого нужно иметь при себе битовые маски(определенный набор битов, которые используются для выбора отдельных битов, или нескольких битов ). Рассмотрим примеры.
Для того чтобы проверить четность числа, нам достаточно проверить самый первый бит, чему он равен, если 1 то число нечетное, если 0 значит четное,
dec       binary

0           00000000
1           00000001
2           00000010
3           00000011
4           00000100

как было сказано, нас интересует первый бит, тот который крайний справа, все отстальные биты можно не рассматривать, значит нам нужно наше число(которе проверяем на четность) побитово умножить на маску, так как 7 из 8 битов нас не интересуют, то получаем такую вот маску - 00000001. Теперь это можно проверить на практике.
число 123 - нечетное, в битовом представлении это 01111011, умножаем на маску:
   01111011
&
   00000001

=
   00000001
Если результат после умножения отличный от 0, значит число нечетное.
if(X & 00000001) 
  нечетное

#include <stdio.h>
#include <stdlib.h>

#define BIT_0 0b00000001 // or 0x01 or 1

int main()
{
  for(int i = 0; i < 10; ++i)
  {
    unsigned int value = rand() % 1000;
    if( value & BIT_0 )
      printf("%u is odd\n", value);
    else
      printf("%u is even\n", value);
  }
  return 0;
}

Аналогично можно проверить все остальные биты. В начале этого сообщения, есть функция print_bit_byte которая печает состояния битов в байте, применяется операция &.

|     - побитовое ИЛИ
Можно назвать сложением(для простоты запоминания), соответственно - 0 сложить с 0 будет 0, 1 сложить с 0 будет 1, 1 сложить с 1 будет 1.

    0101
| 
    0011
=
    0111  

Примеры использования этой операции и других, будут внизу. Примеров должно быть много.

^    - исключающее ИЛИ (XOR)
Лучше никак не называть кроме как XOR :-) чтобы не вносить путаницу. Два одинаковых по значению бита, дают 0, два различных по значению дают 1
    0101
^
    0011
=
    0110  

>>  - побитовый сдвиг вправо

<<  - побитовый сдвиг влево
Сдвиг на определенное количество битов вправо или влево.

Сдвиг влево    E1(что сдвигаем) << E2(на сколько)
Биты справа заполняются нулями.
Если E1 имеет знаковый тип(signed) и отрицательное значение, то результ операции неопределен.

Сдвиг вправо  E1(что сдвигаем) >> E2(на сколько)
Биты слева заполняются нулями. !НО! Если E1 имеет знаковый тип и отрицательное значение, то результат зависит от реализации этой операции процессором(implementation-defined), для процессоров Intel, при такой ситуации, биты слева могут заполняются единицами.

00000001 << 1 = 00000010

00000010 << 1 = 00000100

00000100 << 2 = 00010000

00000100 >> 2 = 00000001

00000001 >> 2 = 00000000

Теперь перейдем к примерам.

Установить нужный бит в 1

unsigned set_bit(unsigned aValue, unsigned aNumber)
{
  return aValue | (1 << aNumber);
}

int main()
{
  unsigned test = 0b00000000;
  test = set_bit(test, 0);  // 00000001
  test = set_bit(test, 7);  // 10000001
  return 0;
}

Очистить нужный бит(сбросить, установить в 0)

unsigned clear_bit(unsigned aValue, unsigned aNumber)
{
  return aValue & (~(1 << aNumber));
}

int main()
{
  unsigned test = 0b10000001;
  test = clear_bit(test, 0);  // 10000000
  test = clear_bit(test, 7);  // 00000000
  return 0;
}

Инвертировать нужный бит (0 в 1, 1 в 0)

unsigned invert_bit(unsigned aValue, unsigned aNumber)
{
  return aValue ^ ( 1 << aNumber);
}

int main()
{
  unsigned test = 0b10000001;
  test = invert_bit(test, 0);  // 10000000
  test = invert_bit(test, 7);  // 00000000
  test = invert_bit(test, 7);  // 10000000
  return 0;
}

Тест нужного бита (установлен он в 0 или 1)

unsigned test_bit(unsigned aValue, unsigned aNumber)
{
  return aValue & (1 << aNumber);
}

int main()
{
  unsigned test = 0b10000001;
  if(test_bit(test, 0))
    printf("Bit 0 is 1\n");
  else
    printf("Bit 0 is 0\n");

  if(test_bit(test, 1))
    printf("Bit 1 is 1\n");
  else
    printf("Bit 1 is 0\n");
  return 0;
}

Подсчет количества единичных битов.
Для того чтобы подсчитать количество единичных битов можно использовать следующую операцию x&(x-1)
Суть этой операции в том что самый младший единичный бит устанавливается в 0, соответственно выполняя в цикле эту операцию над значением, можно подсчитать количество единичных битов, которое будет равно количеству итераций.
0b01001011 - количество единичных битов 4
считаем:
0b01001011 & (0b01001011 - 1) = 0b01001010
0b01001010 & (0b01001010 - 1) = 0b01001000
0b01001000 & (0b01001000 - 1) = 0b01000000
0b01000000 & (0b01000000 - 1) = 0b00000000

unsigned n_of_s_bits(unsigned aValue)
{
  unsigned res = 0;
  while(aValue)
  {
    aValue = aValue & (aValue - 1);
    res++;
  }
  return res;
}

int main()
{
  unsigned test = 0;

  test = 0b00000000;
  printf("Number of single bits for %u = %u\n", test, n_of_s_bits(test));

  test = 0b11111111;
  printf("Number of single bits for %u = %u\n", test, n_of_s_bits(test));

  return 0;
}

Обмен двух значений без использования временной переменной.
Все знают как обменять значения двух переменных с помощью временной переменной.

void swap(int *a, int *b)
{
  int tmp = *a;
  *a = *b;
  *b = tmp;
}
int main()
{
  int a = 1;
  int b = 2;
  swap(&a, &b);
  return 0;
}

Но не все знают как это сделать без временной переменной :-), с помощью XOR, код ниже.

void swap_xor(int *a, int *b)
{
  *a = *a ^ *b;
  *b = *b ^ *a;
  *a = *a ^ *b;
}
int main()
{
  int a = 100;
  int b = -100;
  swap_xor(&a, &b);
  return 0;
}

Один из алгоритмов генерации случайных чисел, разработанный Джорджом Марсаглием,
xorshift (больше примеров по ссылке)

#include <stdio.h>
#include <stdint.h>

/* The state word must be initialized to non-zero */
uint32_t xorshift32(uint32_t state[static 1])
{
  uint32_t x = state[0];
  x ^= x << 13;
  x ^= x >> 17;
  x ^= x << 5;
  state[0] = x;
  return x;
}

int main()
{
  uint32_t state[1] = {1};
  printf("%u\n", xorshift32(state));
  printf("%u\n", xorshift32(state));
  printf("%u\n", xorshift32(state));
  return 0;
}

Использование XOR также применяется в шифровании, ниже пример простого шифрования на основе XOR и ключа шифрования, его недостатком является то что зная часть исходных данных можно вычислить ключ, но такой прием используется как маленькая часть больших и сложных алгоритмов шифрования.

#include <stdio.h>
#include <string.h>

void encrypt_str(const char *apStr, const char *apKey, char *apOutStr)
{
  unsigned strLength = strlen(apStr);
  unsigned keyLength = strlen(apKey);
  unsigned key_i     = 0;

  for(unsigned i = 0; i < strLength; ++i)
  {
    apOutStr[i] = apStr[i] ^ apKey[key_i++];

    if(key_i >= keyLength)
      key_i = 0;
  }
}

void decrypt_str(const char *apStr, const char *apKey, char *apOutStr)
{
  unsigned strLength = strlen(apStr);
  unsigned keyLength = strlen(apKey);
  unsigned key_i     = 0;

  for(unsigned i = 0; i < strLength; ++i)
  {
    apOutStr[i] = apStr[i] ^ apKey[key_i++];

    if(key_i >= keyLength)
      key_i = 0;
  }
}

int main()
{
  char *originStr = "!! Hello encrypt !!";
  char *key = "cCppProsto";

  char encrypt_buffer[100] = {0};
  char decrypt_buffer[100] = {0};

  encrypt_str(originStr, key, encrypt_buffer);
  decrypt_str(encrypt_buffer, key, decrypt_buffer);

  printf("original: %s\n", originStr);
  printf("key     : %s\n", key);

  printf("encrypted - %s\n", encrypt_buffer);
  printf("decrypted - %s\n", decrypt_buffer);
  return 0;
}

Если зашифрованную строку проксорить оригинальной то мы получим ключ :-)

XOR также може применяется для шифрования данных, к примеру данные храняться на 3-х дисках, первый хранит половину информации, второй вторую половину, третий результат XOR обеих данных первых двух дисков. Для расшифровки данных достаточно двух любых дисков.

Определить имеют ли два числа, противоположные знаки

#include <stdio.h>
int main()
{
  int a = 100;
  int b = -1;
  if( ( ( a^b ) < 0 ) )
    printf("%i and %i have opposite signs\n", a, b);
  else
    printf("%i and %i have the same sign\n", a, b);
  return 0;
}

Установить или сбросить биты по маске

int main()
{
  // 0 - clear bits by mask,
  // 1 - set bits by mask
  int isSb = 1; // is set bits

  unsigned mask  = 0b01110001;
  unsigned value = 0b10001110;

  value = (value & ~mask) | (-isSb & mask); // 0b11111111
  isSb = 0;
  value = (value & ~mask) | (-isSb & mask); // 0b10001110

  return 0;
}

Много интересных примеров также есть !здесь! (некоторые из которых присутствуют в этом посте.)