Комментарии 104
/*
Hamming encode/decode
MP3 0 0 0 0 0 0 0 1 1 1 1 0
MP2 0 0 0 1 1 1 1 0 0 0 0 1
MP1 0 1 1 0 0 1 1 0 0 1 1 0
MP0 1 0 1 0 1 0 1 0 1 0 1 0
D0 D1 D2 D3 D4 D5 D6 D7 C0 C1 C2 C3 C4 C5 C6 C7 C8 C9 CA CB
B0 B1 B2 B3 B4 B5 B6 B7 <==> P0 P1 B0 P2 B1 B2 B3 P3 B4 B5 B6 B7
** ** ** ** ** ** ** **
data_byte hamming_code (L=C0..C7, H=C8..CB)
P0=C0 xor C2 xor C4 xor C6 xor C8 xor C10
P1=(C1 xor C2) xor (C5 xor C6) xor (C9 xor C10)
P2=(C3 xor C4 xor C5 xor C6) xor (CB)
P3=(C7 xor C8 xor C9 xor CA)
P3_0 -> 0-no_error, 1..12 invalid bit number
Hamming encode D7_0 ==> C11_0
Hamming decode C11_0 ==> D7_0
*/
int hamming_parity(int x) {
int i,p;
for(p=0, i=1;i<=12;++i) { if (x&1) p^=i; x>>=1; }
return p;
}
int hamming_encode(int x) {
int p,r;
r=((x<<4)&0x0F00)|((x<<3)&0x0070); if (x&1) r|=4; // encode
p=hamming_parity(r); r|=p&3; if (p&4) r|=0x0008; if (p&8) r|=0x0080; // set parity
return r;
}
int hamming_decode(int x) {
int p,r;
p=hamming_parity(x); if (p) x^=1<<(p-1); // correcting error
r=((x>>4)&0xF0)|((x>>3)&0x0E); if (x&4) r|=1; // decode
return r;
}
xor eax, ebx
xor ebx, eax
xor eax, ebx
vs
mov ecx, eax
mov eax, ebx
mov ebx, ecx
я и забыл про него.
вот что значит долгое отсутствие практики :(
но мне по старой памяти всё равно кажется, что арифметика на х86 в разы шустрее передачи значений. могу и ошибаться.
Ну и вообще, я бы данный пост назвал «питонисты познают то, что очевидно для сишников» )
за то, что он считает каждый байт на вес золота (и каждый такт заодно),
то человек должен тихо уйти оттуда — и пусть они там поубивают
друг друга.
Это справедливо если код будет выполнятся немного и у себя. А если это миллиарды повторений на всех компьютерах мира?
Хотя есть, конечно, и своя выгода в оптимизации — например, охват аудитории, которая сможет пользоваться программой с комфортом на своём железе.
p.s. Поставить другой контроллер было уже не вариантом, так что пришлось корячиться.
p.p.s. И я там написал много комментариев на тему почему это сделано так и сколько это экономит байт, хоть вроде и не очевидно что экономит.
Я регулярно пользуюсь XOR — например, для проверки, не изменилось ли отслеживаемое значение. Такой вот волшебник XOR, несущий свет XOR в массы :)
Оптимизировать руками это можно после того, как удалось доказать, что результат оптимизации положительный и больше погрешности измерений.
If a memory operand is referenced, the processor’s locking protocol is automatically implemented for the duration of the exchange operation, regardless of the presence or absence of the LOCK prefix or of the value of the IOPL.
Может выйти и медленнее, чем через промежуточный регистр.
Вот эта вот штука с обменом через XOR имеет настолько узкоспециальное применение, что я вот даже не помню использовал ли это хоть где-нибудь за 30 лет написания программ. Очень может быть что использовал в 90-х в демо на Спекки, когда нужно было считать каждый такт и каждый регистр процессора был на вес золота.
x ^= y;
y ^= x;
x ^= y;компилируется в
mov eax, DWORD PTR [rbp-8]
xor DWORD PTR [rbp-4], eax
mov eax, DWORD PTR [rbp-4]
xor DWORD PTR [rbp-8], eax
mov eax, DWORD PTR [rbp-8]
xor DWORD PTR [rbp-4], eaxА код
z=x;
x=y;
y=z;соответственно в
mov eax, DWORD PTR [rbp-4]
mov DWORD PTR [rbp-12], eax
mov eax, DWORD PTR [rbp-8]
mov DWORD PTR [rbp-4], eax
mov eax, DWORD PTR [rbp-12]
mov DWORD PTR [rbp-8], eaxВыигрыш от этой конструкции на языках высокого уровня только моральный (экономия 1 переменной).
x ^= y;Извините, вы, кажется, '-O2' уронили… Вот, держите: https://godbolt.org/z/rPb4dh
y ^= x;
x ^= y;
компилируется в
mov eax, DWORD PTR [rbp-8]
xor DWORD PTR [rbp-4], eax
....
Можно же без XOR и без доп переменных:
a=a+b;//a+b
b=a-b;//a+b-b=a
a=a-b;//a+b-a=b
область применения a,b=<Max_переменной/2, а у метода с XOR нет
Нет. Границы применимости у методов абсолютно одинаковые.
И что? Пока сами a и b влазят в машинное слово (а иначе задача лишена физического смысла) все работает, независимо от переполнений, возникших при промежуточных вычислениях.
Смотрите: пусть, для простоты понимания кожаными мешками, машинное слово — два десятичных разряда.
a=98
b=99
a = a+b = 98+99 = 197 97 // переполнение при сложении
b = a-b = 97-99 = -2 98 // переполнение при вычитании
a = a-b = 97-98 = -1 99 // переполнение при вычитании
У нас во всех трех операциях возникало переполнение, и тем не менее мы получили правильный результат. Модульная арифметика она такая
crc32( a ) ^ crc32( b ) ^ crc32( c ) = crc32(a ^ b ^ c)
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef unsigned uint;
uint crc32(const char* data,int size,uint crc=0) {
crc=~crc;
for(int i=0;i<size;i++) {
crc^=data[i]&255;
for(int j=0;j<8;j++) crc=crc>>1^0xEDB88320&-(crc&1);
}
return ~crc;
}
int main(int argc, char const *argv[]) {
enum { n=10 };
char payload[n+4];
srandom(time(0)); for(int i=0;i<n;i++) payload[i]=random();
uint payload_crc=crc32(payload,n);
printf("crc(payload)=%08X\n",payload_crc);
uint x=0xBEDA;
char xd[4]={x,x>>8,x>>16,x>>24};
uint xd_crc=crc32(xd,4);
uint suffix=payload_crc^x;
payload[n ]=suffix;
payload[n+1]=suffix>>8;
payload[n+2]=suffix>>16;
payload[n+3]=suffix>>24;
uint crc=crc32(payload,n+4);
printf("crc(data )=%08X\n",crc);
printf("crc(x )=%08X\n",xd_crc);
return 0;
}crc(payload)=116441E8
crc(data )=A76D55FB
crc(x )=A76D55FB
Это другой человек, увидев такое краткое, быстрое и при этом непонятное ему решение, почувствует свою неполноценность. А это ведь это и есть высшая цель программиста-автора. %))
Но если есть возможность писать с первого взгляда понятный код — надо именно так и делать.
Ещё одно замечательное свойство — проверка существования выигрышной стратегии и решение игры "ним" (а также всех эквивалентных ей): https://e-maxx.ru/algo/sprague_grundy
Мы складываем все потенциальные целые числа, а затем вычитаем те, которые встречаются на самом деле. Это решение не такое красивое, потому что придётся обрабатывать переполнения, а также потому что тип элементов должен поддерживать +, — с определёнными свойствами.
Для указанных в условии задачи целых чисел такой тип элементов называется int.
И нет, как ни странно, обрабатывать переполнения никакой необходимости нет.
Switch eax
Case A:
…
Case B:
…
Case C:
....
То получится следующее:
xor eax, A
jz A_label
xor eax, A^B
jz B_label
xor eax, B^C
jz C_label
xor eax, C^D
jz D_label
jmp Default_Label
VLIW позволяет сделать rA=rB; rB=rA в одном пакете и не париться с промежуточным регистром
Дан массив A из n — 2 целых чисел, находящихся в интервале от 1 до n. Все числа встречаются ровно один раз, за исключением двух отсутствующих чисел. Найти эти два отсутствующих числа.
…
После применения предыдущего алгоритма у нас останется u ^ v. Что можно сделать с этим значением? Нам каким-то образом нужно извлечь из него значения u и v, но не совсем понятно, как это сделать.
А можно по рабоче-крестьянски пояснить, на пальцах:
n = 5
u^v = 1
какие именно два числа из исходного набора 1,2,3,4,5 были пропущены ?
Нашли z = u ^ v
Теперь z смотрим побитово, например он (0,0,0,0,1,0,1,0)
Понимаем что в числах u и v есть отличие в пятом бите и в седьмом, берем только первое отличие в пятом бите.
Теперь исходные массивы A и N делим на 2 части, в массивы A1,N1 заносим все числа из A и N в которых пятый бит равен 0, в массивы A2 и N2 заносим все числа из A и N в которых пятый бит равен 1.
Теперь мы точно знаем что u и v находятся/отсутствуют в разных массивах, которые мы создали. Остается прогнать алгоритм для нахождения одного пропущенного/избыточного числа для A1,N1 и A2,N2 по отдельности, и мы найдем u и v.
Задача, фактически, сведена к предыдущей — есть множество известных элементов, из которого один отсутствует. Снова xor'им, чтобы найти u (или v), далее оставшееся.
A = 2, 3, 4, 1, 2, 5, 3
XOR(A,N) = 3 ^ 2 = 1 (1 0 0 0 0 0 0 0), отличие в первом бите
Делим
N1 = 2, 4
A1 = 2, 4, 2
N2 = 1, 3, 5
A2 = 3, 1, 5, 3
Считаем
XOR (N1, A1) = 2
XOR (N2, A2) = 3
Нашли искомое
Это все, конечно здорово. Но загадал я 4 и 5 :)
N = 1, 2, 3, 4, 5
A = 2, 5, 4, 1, 4, 5, 3
XOR(A,N) = 4 ^ 5 = 1 (1 0 0 0 0 0 0 0), отличие в первом бите
Делим
N1 = 2, 4
A1 = 2, 4, 4
N2 = 1, 3, 5
A2 = 5, 1, 5, 3
Считаем
XOR (N1, A1) = 4
XOR (N2, A2) = 5
Проекция u ^ v необратима однозначно, и даст одинаковое значение для бесконечного числа пар различных u и v.
Поиск 2 недостающих чисел с помощью xor уже слишком искусственный и вряд ли имеет смысл. Он требует 2 N доп. памяти и O(N) операций xor и сравнений. Имея столько памяти за столько сравнений, можно более эффективный алгоритм поискать. Навскидку.
N = new int[n];
for (int a: A) N[a]++;Получили в массиве N количество вхождений каждого элемента множества.
Каким образом можно создать 4 множества из 2N элементов, не потратив память?
Алгоритм такой:
1. Посчитайте u^v (как xor всего множества A xor range).
2. Выберите бит, в котором есть расхождение между u и v (пусть это бит i).
3. Посчитайте xor {x \in A, x_i = 1} xor {x \in range, x_i = 1} — это u
4. Посчитайте xor {x \in A, x_i = 0} xor {x \in range, x_i = 0} — это v
Пройтись по числам 1..n и по массиву A[n] и у каждого элемента проверять включен-ли i-й бит. Если да, то сделать ^ c переменной агрегатором. В конце процедуры в переменной будет содержаться u. Сделав ^ c u^v, найдем v. Никакой дополнительной памяти, множества строятся "на лету" — просто проверяется входит-ли в него данный элемент.
Дан массив A из n — 1 целых чисел, находящихся в интервале от 1 до n. Все числа встречаются в нём ровно один раз, за исключением одного отсутствующего числа. Найти это отсутствующее число.
Сумма ряда от 1 до N считается моментально. Сумма чисел в массиве — за 1 проход. Разница == пропущенное число. И никакой магии, кроме школьной математики ;)
Некоторые хорошо готовились к тесту, а именно: заранее находили подобные файлы, вскрывали пароль на макросы и смотрели алгоритм. Далее дело техники: XOR числа нужной колонки с пятикратным номером вопроса давал правильный ответ. Делалось с помощью виндового калькулятора даже без перехода в режим Программист горячей клавишей.
Потом прикрыли лавочку, стали собирать файлы с ответами и отправлять их в 1С.
Сейчас всё онлайн, конечно.
Хороший код, это понятный и быстрый.
Если элементарные операции вам не понятны, значит вы не туда свернули)
Да, трюки, хаки это все для выпендрежа, возможно для собесов, где проверяют не ваши умения, а на насколько глубоко вы копнули в мануалы, те тестируют глубину ваших знаний. А в работе подобное точно использовать нельзя, так как команда может состоять из специалистов разного уровня и код должен быть простой понятный для всех, а не только для гиков
Ещё можно заметить, что 2n^(2n+1)=1
Это поможет упростить первый цикл. Если n четное, то result после него будет 0, если нечётное, то n+1
Пните, если ошибся
Тут не 0 и не n+1
Для нечётного n последовательность 0...n разбивается на парные блоки вида [2x, 2x+1], где x — целое и неотрицательное. Число таких блоков составляет (n + 1) / 2.
Каждый блок сокращается в 1 при взятии операции xor внутри блока. Соответственно вся последовательность операций xor сокращается в xor от (n + 1) / 2 единиц. Если (n + 1) / 2 — чётное, то конечный результат 0, в противном случае 1.
Для чётного n можно просто посчитать результат xor последовательности для n-1, и сделать xor с n. Получится либо n (при xor с 0), либо n + 1 (при xor с 1).
Это не только просто, но и быстрее, потому что первый цикл («сложить все числа диапазона») можно сократить до одной строчки — вычисление суммы арифметической прогрессии.
Применяем XOR ко всем элементам, запоминаем результат:
P = A[0] ^ A[1] ^… ^ A[n — 1]
После этого, поочередно выполняя XOR со всеми числами от 1 до n, находим такое значение, что XOR этого значения с P даст результат, отличный от P. Это и будет искомое число.
Еще если сделать XOR и затем посчитать единичные биты(popcount) можно найти расстояние Хэмминга.
На самом деле, только коммутативности и "х^х=0" недостаточно. Необходимо, чтобы операция была ещё и ассоциативна — когда мы пишем а^b^c, мы подразумеваем (а^b)^c, и по-хорошему нужно доказать, что это выражение равно а^(b^c). Можно так же с помощью таблиц.
"Достигнуть предела" и поиметь XOR для большего числа состояний чем 2 можно опустившись глубже в терминологии. XOR это побитовая четность значений (ну или поразрядные суммы по модулю 2) Тут возникает даже 2 подхода к увеличению показателя. Можно все пересчитать в троичной системе, а можно двоичные разряды складывать в троичный накопитель. Но подумав еще немного станет понятно, что эффективнее подниматься сразу до 4-ичной системы. И так как нам не важен порядок разрядов (т.к. XOR его игнорирует по определению) можно все входящие значения "преобразовывать рассческой"
toQuaternit=(x)=> x&0x5555 | (x&~0x5555)<<15 //получая исходные 16 бит в позициях 32битного 0x55555555затем с пред коррекцией можно складывать по модулю 3 (по сути это троичный XOR)
addBitMod3=(sum, x){
let quaternit = x&0x5555 | (x&~0x5555)<<15;
let msk = ~3*(sum>>1 & quaternit) //4-чные разряды ожидающие сложения и уже >=2
return (sum&msk) //коррекция переполнения
+ (quaternit&msk); //сложение остальных
// после которого 4ичные разряды 0<=2 (что эквивалентно вычислениям в 3ичной)
}Кстати говоря если вы параллельно с этим сделаете обычный 2-чный XOR по элементам, то из них обоих можно будет однозначно получить 6-чный XOR. И вообще пройдя так несколько-ичными XOR'ами вы получите XOR'ы всех их комбинаций (так что интереснее всего брать простые числа)
4-чная система конечно с другими коррекциями тоже считается, и даже пребывает в нормальной для компьютера форме. Т.е. в нее не надо переводить значения потому что 2чка ей кратна.
Upd: И конечно XOR далеко не только для экономии память на хаках... высокоуровневые программисты об этом узнают часто поздно. Он активно используется в алгоритмах избыточных данных с кодами коррекции. В прикладных нуждах к нему часто можно свести флаги хитро индексирующие БД и там это может заменять крайне тормознутые развернутые формы запросов.
Трюк с XOR для собеседований и не только