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

Предыдущий"Веселый бинарник"Мы говорили о некоторых базовых знаниях двоичного кода, но не говорили о битовых операциях. Некоторым студентам этого было мало. В этой статье в основном объясняется использование операций с младшими битами. Давайте начнем с примера, надеясь вдохновить всех . Не забудьте отметить применение следующего примера, это очень поможет.

1. Судоку

Судоку — хороший пример введения битовых операций, и существует большая разница в эффективности между использованием битовых операций и их неиспользованием. Давайте сначала посмотрим на требования судоку:

1. Где текущий номерРядРисунки 1-9 включительно, повторяться не будут.

2. Где текущий номерСписокЧисла содержат от 1 до 9 без повторения

3. Где текущий номердворец(т.е. крупная сетка 3х3) все числа содержат от 1 до 9, не повторяются (дворец, как показано на рисунке ниже, каждая толстая линия - это дворец)

,

1. Обычный алгоритм

Если мы используем обычный метод, то каждый раз, когда мы вводим число, нам нужно проверять текущую строку, столбец и есть ли повторяющиеся числа в других позициях во дворце, В крайнем случае нам нужно зациклить 27 (3 * 9) раз проверить. Давайте посмотрим на обычный алгоритм проверки.

	int check(int sp) {
	   // 檢查同行、列、九宮格有沒有相同的數字，若有傳回 1
	   int fg= 0 ;
	   if(!fg) fg= check1(sp, startH[sp], addH) ;   // 檢查同列有沒有相同的數字
	   if(!fg) fg= check1(sp, startV[sp], addV) ;   // 檢查同行有沒有相同的數字
	   if(!fg) fg= check1(sp, startB[sp], addB) ;   // 檢查同九宮格有沒有相同的數字
	   return(fg) ;
	}

	int check1(int sp, int start, int *addnum) {
	   // 檢查指定的行、列、九宮格有沒有相同的數字，若有傳回 1
	   int fg= 0, i, sp1  ;
	   //万恶的for循环
	   for(i=0; i<9; i++) {
	      sp1= start+ addnum[i] ;
	      if(sp!=sp1 && sudoku[sp]==sudoku[sp1]) fg++ ;
	   }
	   return(fg) ;
	}

Страшна ли такая оперативность?Каждый раз заполняя, нужно проверять 27 раз.Есть алгоритм проверки один раз? Конечно, есть, используя битовые операции, один раз. Давайте посмотрим на идею следующей битовой операции:

2. Битовая операция

Как показано на рисунке выше, данные одной строки (или столбца, дворца) содержат в общей сложности 9 чисел от 1 до 9, которые мы вместе называем числом девяти дворцов. Если мы используем двоичный код,Число из девяти квадратов используется в качестве битовой координаты двоичных данных, а 9-битное двоичное может использоваться для соответствия одному из них.Если в бите есть данные, идентификация равна 1, а неданные помечен как 0. Такое положительное число может решить состояние строки данных из девяти квадратов.Не нужно хранить массив.

Например, глядя на темно-красную часть рисунка, в текущих девяти дворцовых данных уже есть 1 и 3, тогда первый и третий биты справа двоичного кода помечены как 1, а число 5 может сохранить текущая строка (или столбец, дворец) состояние массива Теперь, если число равно 511, это означает, что все числа в Девяти Домах были израсходованы, как показано в первой строке рисунка.

проверить занят ли номер, можно ли его занятьБитовая операция, чтобы получить k-й бит правильного числа в двоичном формате, чтобы увидеть, равен ли он 1, если он равен 1, это означает, что указанный номер занят. Рассмотрим конкретный алгоритм проверки:

	// sp 是当前位置索引，indexV 行索引，indexH 列索引，indexB九宫格索引
	int check(int sp,int indexV,int indexH,int indexB) {
	   // 检查同行、列、九宮格沒有用到的数字，若已经用过返回 1
		int status = statusV[indexV]|statusH[indexH]|statusB[indexB];
		//9个数字都被用了
		if (status>=STATUS_MAX_VALUE)
		{
			return 1;
		}
		int number=sudoku[sp];
		//取右数第k位,若是1表明这个值已经存在了
		return status>>(number-1)&1;
	}

	// 行、列、宫二进制数据指定位置标记为1
	int markStatus(int indexV,int indexH,int indexB,int number){
		if (number<1)
		{
			return 0;
		}
		//把右数第k(从1计数)位变成1 
   	  	statusV[indexV]|=(1<<(number-1));
    	statusH[indexH]|=(1<<(number-1));
    	statusB[indexB]|=(1<<(number-1));
	}

В качестве примера возьмем следующее местоположение легенды, как получить числа, которые можно заполнить в текущем местоположении.

Видно, что 2-битная операция решает операцию проверки доступных чисел, в то время как предыдущий обычный алгоритм требовал для ее получения 27 поисков. Конечно, этот алгоритм также можно оптимизировать, например, использовать эвристический DFS для поиска доступных номеров, что быстрее и кликабельно, если вам интересно.здесь.

Я загрузил код обычного алгоритма и алгоритма битовой операции на языке C. Если вы хотите узнать больше, нажмите на ссылку ниже и проверьте сами. (обычный алгоритм гугла)

адрес:Обычный алгоритм судоку,Побитовая версия судоку

2. Основы

1, побитовый оператор

Уведомление:

1. Битовые операции можно применять только к целым числам, а не к числам с плавающей запятой и двойным числом.

2. Кроме того, логические символы сдвига вправо различаются в разных языках, например, в java >>>.

3. Приоритет работы операторов побитовых операторов относительно низкий. Используйте скобки максимально возможным, чтобы обеспечить порядок операций. Например, 1 и I + 1 будет выполнять I + 1 сначала, а затем выполнить &.

3. Примеры применения

Это отличный пример приложения, вы можете отметить его для дальнейшего использования.

1. Смесь

Пример битовой операции

2. Поменять местами два номера

int swap(int a, int b)  
{  
    if (a != b)  
    {  
        a ^= b;  
        b ^= a;  
        a ^= b;  
    }  
}  

3. Найдите абсолютное значение

int abs(int a)  
{  
    int i = a >> 31;  
    return ((a ^ i) - i);  
}  

4, двоичный поиск 32-разрядное целое число, предшествующее 0

int nlz(unsigned x)
{
   int n;

   if (x == 0) return(32);
   n = 1;
   if ((x >> 16) == 0) {n = n +16; x = x <<16;}
   if ((x >> 24) == 0) {n = n + 8; x = x << 8;}
   if ((x >> 28) == 0) {n = n + 4; x = x << 4;}
   if ((x >> 30) == 0) {n = n + 2; x = x << 2;}
   n = n - (x >> 31);
   return n;
}

5, двоичный обратный порядок

int reverse_order(int n){

  n = ((n & 0xAAAAAAAA) >> 1) | ((n & 0x55555555) << 1);
  n = ((n & 0xCCCCCCCC) >> 2) | ((n & 0x33333333) << 2);
  n = ((n & 0xF0F0F0F0) >> 4) | ((n & 0x0F0F0F0F) << 4);
  n = ((n & 0xFF00FF00) >> 8) | ((n & 0x00FF00FF) << 8);
  n = ((n & 0xFFFF0000) >> 16) | ((n & 0x0000FFFF) << 16);

  return n;
}

6, число двоичных 1

 unsigned int BitCount_e(unsigned int value) {
        unsigned int count = 0;
        // 解释下下面这句话代码，这句话求得两两相加的结果，例如 11 01 00 10
        // 11 01 00 10 = 01 01 00 00 + 10 00 00 10，即由奇数位和偶数位相加而成
        // 记 value = 11 01 00 10，high_v = 01 01 00 00， low_v = 10 00 00 10
        // 则 value = high_v + low_v，high_v 右移一位得 high_v_1，
        // 即 high_v_1 = high_v >> 1 = high_v / 2
        // 此时 value 可以表示为 value = high_v_1 + high_v_1 + low_v，
        // 可见 我们需要 high_v + low_v 的和即等于 value - high_v_1
        // 写简单点就是 value = value & 0x55555555 + (value >> 1) & 0x55555555;
        value = value - ((value >> 1) & 0x55555555);

        // 之后的就好理解了
        value = (value & 0x33333333) + ((value >> 2) & 0x33333333);
        value = (value & 0x0f0f0f0f) + ((value >> 4) & 0x0f0f0f0f);
        value = (value & 0x00ff00ff) + ((value >> 4) & 0x00ff00ff);
        value = (value & 0x0000ffff) + ((value >> 8) & 0x0000ffff);
        return value;

        // 另一种写法，原理一样，原因在最后一种解法中有提到
        //value = (value & 0x55555555) + (value >> 1) & 0x55555555;
        //value = (value & 0x33333333) + ((value >> 2) & 0x33333333);
        //value = (value & 0x0f0f0f0f) + ((value >> 4) & 0x0f0f0f0f);
        //value = value + (value >> 8);
        //value = value + (value >> 16);
        //return (value & 0x0000003f);
    }

-----------------------end-------------------------

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

Сканируйте для большего внимания.