Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 103
Алгоритм проверки числа на степень двойки вовсе не рекурсивный.
Факториал быстро ляжет
swap(x,x) не сработает
Странно, правда?
x ^ x = 0
Уточняю: поскольку обе ссылки будут указывать на одну переменную, любой xor будет давать 0.
если честно все равно не понял. если по шагам алгоритм такой:
a = a^b (x^x = 0 => a = 0)
b = a^b (0^x = x => b = x)
a = a^b (0^x = x => a = x)
я подозреваю в данном алгоритме абсолютно не важно какие значения a и b на входе. можно по подробнее объяснить причину ошибки в функции (и моих рассуждениях)?
a = a^b (x^x = 0 => a = 0)
b = a^b (0^x = x => b = x)
a = a^b (0^x = x => a = x)
я подозреваю в данном алгоритме абсолютно не важно какие значения a и b на входе. можно по подробнее объяснить причину ошибки в функции (и моих рассуждениях)?
Причина в том, что если функции в качестве обоих параметров будет передана ссылка на один и тот же объект, то при первом же xor получится 0, поскольку xor любого значения с самим собой даёт 0. При дальнейших вычислениях ничего кроме нуля тоже не получится.
В таком случае алгоритм по шагам будет выглядеть так:
a = a^b (x^x = 0 => a = 0, b = 0, поскольку это один и тот же объект)
b = a^b (0^0)
a = a^b (0^0)
В таком случае алгоритм по шагам будет выглядеть так:
a = a^b (x^x = 0 => a = 0, b = 0, поскольку это один и тот же объект)
b = a^b (0^0)
a = a^b (0^0)
Я всего лишь о том, что краткость это хорошо, но надо, чтобы код корректно работал. Вот gcd правильно работает, а lcm и swap — нет (lcm(0,0) упадёт). Кстати, ещё не работает проверка на степень двойки (неправильный ответ для n = -(2 ^ {31}).
Конечно, lcm(0,0) упадет. Кажется естественным, что нахождение числа, кратного нулю, вызывает ошибку деления на ноль.
И да, в какую степень нужно возвести 2, чтобы получить -(2 ^ 31)?
И да, в какую степень нужно возвести 2, чтобы получить -(2 ^ 31)?
В 31-ю, очевидно. А если возвести в 32-ю, получится 0 — и алгоритм тоже скажет, что это степень двойки.
Вот что плохо, так это что lcm(1,0) и lcm(0,1) вернет 0, а не упадет. :-)
lcm(a,0) = 0, по определению.
Еще с отрицательными не работает.
Нахождение НОК не совсем однострочник. Он же использует GCD.
10-тый достаточно спорный, он сдвигает f1 и f2 дальше по последовательности, но мне не понятен что-то смысл его возвращаемого значения, он возвращает новый f1, какой в этом смысл?
Про обмен значений переменных с помощь исключающего или уже везде, где можно и нельзя обсудили, а вывод один — никогда не используйте этот метод. Тоже самое и с рекурсивными функциями — используйте с крайней осторожностью, если конечно, не на функциональных языках пишете. Имхо, однострочники не нужны — оформляйте код так, чтобы его можно было прочитать и понять без проблем.
исключая 4 и 10 остальное чистый Си
Обмен через xor далеко не быстрее и не короче. Более того, он неочевиднее. Кроме этого, gcc его компилирует в три mov через временный регистр.
Более того, обмен переменных через mov может быть соптимизирован процессором в процессе планирования исполнения команд, а обмен через xor — не может.
function swap(&$a, &$b) {
$a ^= ($b ^= ($a ^= $b));
}
Я Вас обожаю.
Крутое слово — «Алгорытм». Это просто опечатка или какой-то Интернет-мем?
Обмен двух значений шикарен.
Его трехстрочный эквивалент на двух переменных знаю со второго курса, но все равно смотрится круто.
Его трехстрочный эквивалент на двух переменных знаю со второго курса, но все равно смотрится круто.
Своп двух переменных делает UB, так как перемення изменяется дважды в одной sequence point. Скорее всего, не будет работать при определенном сочетании компилятор/флаги.
Число ненулевых битов в числе:
int NBit(unsigned int x){
return x==0 ? 0 : (x&1)+NBit(x>>1);
}
Обычно эту функцию называют popcnt — population count.
Из однострочников можно еще предложить x & 1 + x & 2 +… + x & 32. Хотя самое быстрое решение этой задачи, насколько я помню, — это таблица. Для int'a хранить таблицу накладно, но легко для byte и 4 раза применить: bitsInByte[x & 0xFF] + bitsInByte[x & 0x00FF] и т.д.
Прочие варианты: resnet.uoregon.edu/~gurney_j/jmpc/bitwise.html
Имеется в виду bitsInByte[x & 0xFF]+bitsInByte[(x>>8) & 0xFF]+bitsInByte[(x>>16) & 0xFF]+bitsInByte[(x>>24) & 0xFF]? Я тоже думаю, что это самое быстрое. Можно еще вместо (x>>24)&0xff написать ((unsigned char*)&x)[3]. Но это может оказаться медленнее, через регистры программа может не соптимизировать.
А (x&1)+(x&2)+… я не понял вообще. Или это (x&1)+((x>>1)&1)+((x>>2)&1)+...?
А (x&1)+(x&2)+… я не понял вообще. Или это (x&1)+((x>>1)&1)+((x>>2)&1)+...?
Любой начинающий программист на haskell/scheme/другом_яфп реализовывал эти тривиальные примеры применения рекурсии. В С же везде тут рекурсия является лишней и только замедляет работу программы (особенно ужасен фибоначчи с двойной рекурсией).
Из нерекурсивных обмен переменных — но он весьма затаскан и о недостатках его говорилось очень много.
Из нерекурсивных обмен переменных — но он весьма затаскан и о недостатках его говорилось очень много.
Можно еще вспомнить
void strcpy(char *a,char *b){
while(*a++=*b++);
}
void strcpy(char *a,char *b){
while(*a++=*b++);
}
Вот нашел функцию нахождения площади треуголника
double squareTriangle(int x1, int y1, int x2, int y2, int x3, int y3) {
return abs((x2-x1)*(y3-y1)-(x3-x1)*(y2-y1))/2.0;
}
Максимальная степень двойки, на которую делится n (n!=0):
Найти минимальное 2^n-1, не меньшее a:
while(a&(a+1)) a|=a+1;
Найти k-й бит в массиве int * (считая, что sizeof(int)==4):
int MaxDivPow2(int n){
return n&-n;
}
Найти минимальное 2^n-1, не меньшее a:
while(a&(a+1)) a|=a+1;
Найти k-й бит в массиве int * (считая, что sizeof(int)==4):
int GetBit(int *a,int k){
return (a[k>>5]>>(k&31))&1;
}
Примеры чисто академические, т.к. в настоящее время должна цениться не лаконичность кода, а стоимость его поодержки.
Очень простые алгоритмы, но все же однострочники…
int max(int a,int b) {
return (a>b)?a:b;
}
int min(int a,int b) {
return (a>b)?b:a;
}
Запустите этот вариант нахождения n-ого члена ряда Фибоначчи на 50-ый элемент. И заварите чаю, съешьте еще булок, потом еще чаю…
Можно написать за логарифм N-ое число Фибоначчи по модулю M, но если попробовать уместить реализацию в одну строку, получается каша мала. Только что пробовал :) Всё равно же, если считать не по модулю, то 50-ый элемент не уместится даже в int64, смысла нет его считать.
Очень много из приведенного в статье и комментах (например, как было в примере с
Я как-то привык думать, что однострочники — это показатель «крутости» языка (гляди, сколько полезного я могу сделать всего лишь одной строчкой!). Здесь же и примеры специфические, и особенности языка не используются (ну кроме рекурсии и тернарника).
n & (n-1)
Я как-то привык думать, что однострочники — это показатель «крутости» языка (гляди, сколько полезного я могу сделать всего лишь одной строчкой!). Здесь же и примеры специфические, и особенности языка не используются (ну кроме рекурсии и тернарника).
книга «Алгоритмические трюки для программистов» Генри Уоррена содержит много примеров
Конечно же UB. А у статьи 40 плюсов.
Не знаю, что такое UB, но этот метод не работает, если в функцию передать одинаковые указатели/ссылки.
int *a, *b;
*a = 1;
*b = 2;
b = a;
swap(a, b);
В переменную a записывается 0.
int *a, *b;
*a = 1;
*b = 2;
b = a;
swap(a, b);
В переменную a записывается 0.
конечно есть
en.wikipedia.org/wiki/XOR_swap_algorithm
The body of this function is sometimes seen incorrectly shortened to if (x != y) *x^=*y^=*x^=*y;. This code has undefined behavior, since it modifies the lvalue *x twice without an intervening sequence point.
en.wikipedia.org/wiki/XOR_swap_algorithm
Корректный вариант isPow2:
a && !(a&(a-1))
Для случая a =0
a && !(a&(a-1))
Для случая a =0
Этак можно пойти все книжку «Алгоритмические трюки для программистов» Генри Уоррена реализовывать.
swap занятный, а так — непрактичные игрушки, включая и swap, впрочем
а в некоторых языках однострочники — реальная сила
а в некоторых языках однострочники — реальная сила
Возведение в степень делать за линию, да еще и рекурсивно? Быстрое возведение в степень конечно на пару строк больше занимает, но все же.
int pow(int a, int k) {
if (!k) return 1;
int m = pow(a, k / 2);
(!(k % 2))? m * m * a: m * m;
}
int pow(int a, int k) {
if (!k) return 1;
int m = pow(a, k / 2);
(!(k % 2))? m * m * a: m * m;
}
Посыпаю голову пеплом, не дочитал до конца).
Только вот почему быстрое возведение в степень стало вдруг «Индийским»? И как по мне, два вложенных тернарных оператора — это ужасно.
Только вот почему быстрое возведение в степень стало вдруг «Индийским»? И как по мне, два вложенных тернарных оператора — это ужасно.
«Индийский алгоритм» возведения в степень
www.algolib.narod.ru/Math/IndianPow.html
www.algolib.narod.ru/Math/IndianPow.html
Орфографические ошибки — это по незнанию, или чтобы статью было сложнее искать?
Алгоритм возведения в степень
Стоило сказать, что степень должна быть больше или равной 0, так как при отрицательной степени вы получите Stack overflow.
Всегда удивлялся почему пишут так
а не так:
Аналогичные ситуации:
Накой отрицание в условии ветвления?
int GCD(int a,int b) {
return (!b)?a:GCD(b,a%b);
}а не так:
int GCD(int a,int b) {
return b?GCD(b,a%b):a;
}Аналогичные ситуации:
if(!x) { /* */
} else { /* */ }Накой отрицание в условии ветвления?
Для наглядности?
Может быть, влияет порядок написания кода. Сначала пишем, что полегче, а сложное (существенное) оставляем на потом. Да и читать так проще, особенно, если else-часть — тоже тернарная операция.
Впрочем, у меня обычно получается по-другому, я начинаю со сложной части.
Впрочем, у меня обычно получается по-другому, я начинаю со сложной части.
возможно попытка оптимизации, чтобы ведь оператор if с разной скоростью переходит на разные ветви кода, в ядре линукс для этого используются макросы likely/unlikely
сравните:
это будет:
#define likely(x) __builtin_expect((x),1)
#define unlikely(x) __builtin_expect((x),0)
сравните:
if(likely(a)) {
printf("1");
}
if(unlikely(a)) {
printf("2");
}
это будет:
40049d: 8b 54 24 0c mov edx,DWORD PTR [rsp+0xc]
4004a1: 85 d2 test edx,edx
4004a3: 74 12 je 4004b7 <main+0x37>
4004a5: bf 31 00 00 00 mov edi,0x31
4004aa: e8 a1 ff ff ff call 400450 <putchar@plt>
4004af: 8b 44 24 0c mov eax,DWORD PTR [rsp+0xc]
4004b3: 85 c0 test eax,eax
4004b5: 75 07 jne 4004be <main+0x3e>
4004b7: 31 c0 xor eax,eax
4004b9: 48 83 c4 18 add rsp,0x18
4004bd: c3 ret
4004be: bf 32 00 00 00 mov edi,0x32
4004c3: e8 88 ff ff ff call 400450 <putchar@plt>
4004c8: eb ed jmp 4004b7 <main+0x37>
4004ca: 90 nop
4004cb: 90 nop
Разве современные процессоры не пытаются предсказать условие перехода по статистике срабатываний? После того, как у них сформируется мнение, разницы между первым и вторым вариантом уже не будет: какой вариант процессор выбрал в качестве вероятного, тот и будет считаться быстрее.
P.S. Смотрю я на последовательность call X // jmp Y — и думаю: «кто же так пишет? Надо так: push Y // jmp X — несколько лишних байтов, но один переход экономится».
P.S. Смотрю я на последовательность call X // jmp Y — и думаю: «кто же так пишет? Надо так: push Y // jmp X — несколько лишних байтов, но один переход экономится».
Зато в php можно поменять местами не только целочисленные значения, а любые!
function swap(&$a, &$b)
{
list($b, $a) = array($a, $b);
}
Бе-бе-бе!
function swap(&$a, &$b)
{
list($b, $a) = array($a, $b);
}
Бе-бе-бе!
Статья супер, спасибо автору. Где Вы раньше были? )
Тем, кому понравилось, рекомендую посмотреть про битовые операции Bit Twiddling Hacks — узнаете много нового и интересного.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Однострочники на С++