Комментарии 38
> Есть два целых числа
> в как можно старшем бите этого числа получить единицу
Сразу неправильно, если смотреть формально на задание ;)
> в как можно старшем бите этого числа получить единицу
Сразу неправильно, если смотреть формально на задание ;)
Хорошо бы пару примеров, где это можно использовать. А то какой-то балласт знаний получается, если дополнительно не разбираться в проблеме. На SO есть кучка решений и идей, но нет полноценного сравнения и ремарки по поводу применения.
Сама задача взята отсюда. Было свободное время, хотелось поломать голову и познакомится с чем-нибудь новым. Так появился этот код и статья )
хотелось поломать голову и познакомится с чем-нибудь новым
Заходите на http://codeforces.ru/problemset, там есть задачки интереснее и сложнее.
Ээм… А чего так сложно?
Берем L и R, находим у них самый старший бит, который различается, с битами выше ничего сделать нельзя, биты ниже легко сделать единицами, т.к. если у нас L вида xy...z0..., а R вида xy...z1..., то очевидно, что в промежутке есть числа xy...z011...1 и xy...z100...0.
Берем L и R, находим у них самый старший бит, который различается, с битами выше ничего сделать нельзя, биты ниже легко сделать единицами, т.к. если у нас L вида xy...z0..., а R вида xy...z1..., то очевидно, что в промежутке есть числа xy...z011...1 и xy...z100...0.
«Паттернов начитался»
получается, можно хранить в trie старший бит, который различается и обновлять его при вставке очередного целого числа, а затем делать все биты ниже единицами. Правда сложность все равно будет O(n) = nlogn, но гораздо проще ).
Шта???
Давайте я код напишу, чтобы было понятно: ideone.com/Po4JgL. У того, что я описал сложность — O(log n).
O(n) не равно nlogn
Давайте я код напишу, чтобы было понятно: ideone.com/Po4JgL. У того, что я описал сложность — O(log n).
O(n) не равно nlogn
O(n) = nlogn
Видимо автор всего лишь таким образом записывает фразу «Сложность алгоритма равна nlogn»
Определенно ваше решение проще, да вдобавок еще и быстрее.
Циклы явно лишние ideone.com/qKUwEk
Забавно смотреть на ваши оптимизации, расположенные по соседству со считыванием через cin :)
А чем его заменить? scanf? Это шило на мыло получится. А __builtin_clz на некоторых (x86) платформах разворачивается в одну инструкцию, что магическим образом превращает O(log(n)) в O(1);
Можно заменить на getchar_unlocked() для *nix или getchar() для всех остальных.
getchar_unlocked > getchar > scanf > cin, где ">" означает быстрее.
digital-madness.in/blog/2013/fast-io-in-c/
getchar_unlocked > getchar > scanf > cin, где ">" означает быстрее.
digital-madness.in/blog/2013/fast-io-in-c/
Мы же число вводим, а не символ. Нам строку потом переводить в число придётся.
Дело в том, что высокоуровневые cin и scanf очень медленные по сравнению с getchar_unlocked. Для преобразования входного потока в число можно использовать функцию:
inline int read_int()
{
register int c = getchar_unlocked();
int x = 0;
int neg = 0;
if(c=='-')
{
neg = 1;
c = getchar_unlocked();
}
for(; '0'<=c && c<='9' ; c = getchar_unlocked()) {
x = (x<<1) + (x<<3) + c - '0';
}
return neg ? -x : x;
}
Всё это я видел на stackoverflow, хоть источник бы указывали. Но код должен быть не только производительным, но и выразительным (иногда это даже важнее). Зачем писать по 10 утилитарных функций, зачем в цикле считать биты? Язык предоставляет для всего этого удобные, безопасные инструменты, и не стоит игнорировать их. Я там ещё и bitset использую для красивого вывода в cout. Если всё это писать самому, то решение задачки в 1 строчку превратится в очередной фреймворк. Ведь код я не усложнял, я его значительно упростил. 5 — 6 битовых операций это не так сложно.
Источник указан в комментарии выше, читайте внимательней.
- Про выразительность: выразительность это несомненно важно, но в угоду выразительности жертвовать производительность там, где важна производительность все же не стоит. Речь шла именно о производительности
Забавно смотреть на ваши оптимизации, расположенные по соседству со считыванием через cin
- Про циклы:
зачем в цикле считать биты
Любое число — совокупность бит. В угоду производительности, там где это оправданно, а в этом случае это оправданно — можно и биты посчитать. К тому же решение весьма простое и абстракция в виде функции несомненно проста в использовании и потому эффективна.
и не стоит игнорировать их
Тезис верный, но не стоит принимать его за аксиому. Всему свое место и там где уместно использование готовых функций конечно же не стоит городить велосипеды.
5 — 6 битовых операций это не так сложно
не понимаю тогда чем решение, предложенное мной, сложно.
Я бы сказал — ксорим максимальное возможное число с нулем и получаем искомое.
И я тут подумал — а на что он декартово всунул, когда это декартово можно хранить неявно.
Итак, моё решение. i-й бит перекрывает все биты от 0 до i−1. Потому если удастся i-й бит сделать единицей, его СТОИТ делать единицей, чхая на то, что все низшие будут нулями.
Скорость — кол-во битов в слове.
Итак, моё решение. i-й бит перекрывает все биты от 0 до i−1. Потому если удастся i-й бит сделать единицей, его СТОИТ делать единицей, чхая на то, что все низшие будут нулями.
результат := 0
текБит := максБит()
пока текБит ≠ 0
новРез := результат + текБит
если новРез <= Б
то результат := новРез
текБит >>= 1
Скорость — кол-во битов в слове.
Все-таки стоило прочитать статью перед написанием этого комментария…
Пардон, ошибся, решив не ту задачу.
результатА := 0
текБит := максБит()
пока текБит ≠ 0
новРезБ := результатА + текБит
новРезА := результатА + текБит − 1
если новРезБ > R то
ничего не делать
иначе если новРезА < L то
результатА := новРезБ
иначе
результатА := новРезА
результатБ := новРезБ
стоп
текБит >>= 1
результатБ := результатА // перестраховка
int maxxor(int a,int b){
int c=a^b;
if(c<0) c=max(~a,b);
while(c&(c+1)) c|=c>>1;
return c;
}
Проверил для a,b между -30 и 30 — совпадает с переборным решением.
Или я чего-то не понял в задаче?
НЛО прилетело и опубликовало эту надпись здесь
Добавьте небольшое пояснение вашего подхода.
Я так писать не стал, потому что, во-первых, используется конкретная разрядность, а во-вторых — 7 строчек вместо трёх.
for(k=1;c&(c+1);k<<=1) c|=c>>k;
Тогда для знаковых 32-битных L и R, L <= R так:
18 операций, не считая копирований.
int maxxor(int L,int R){
int c=L^R;
int d=~L|R;
c=(c|(c>>31))&(d|(d>>31));
c|=c>>1;
c|=c>>2;
c|=c>>4;
c|=c>>8;
return c|(c>>16);
}
18 операций, не считая копирований.
Вот мое решение:
Находим самый старший бит который различается. Начиная с него и до самого младшего бита всегда можно сделать единички после xor.
int maxXor(int l, int r) {
unsigned q = l ^ r;
int t = 0;
while(q >> 1) {
t++;
q>>=1;
}
// заполняем все единичками. 2^(t-1) - 1
return (1u<<(t+1)) - 1;
}
Находим самый старший бит который различается. Начиная с него и до самого младшего бита всегда можно сделать единички после xor.
Интереснее задача найти максимум и минимум для A&B, где L1 <= A <= R1, L2 <= B <= R2.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Максимальное XOR