Максимальное XOR

[@nerudo]

> Есть два целых числа
> в как можно старшем бите этого числа получить единицу

Сразу неправильно, если смотреть формально на задание ;)

[@Xlab]

Хорошо бы пару примеров, где это можно использовать. А то какой-то балласт знаний получается, если дополнительно не разбираться в проблеме. На SO есть кучка решений и идей, но нет полноценного сравнения и ремарки по поводу применения.

[@isxaker]

Сама задача взята отсюда. Было свободное время, хотелось поломать голову и познакомится с чем-нибудь новым. Так появился этот код и статья )

[@VladX]

хотелось поломать голову и познакомится с чем-нибудь новым

Заходите на http://codeforces.ru/problemset, там есть задачки интереснее и сложнее.

[@freopen]

Ээм… А чего так сложно?

Берем L и R, находим у них самый старший бит, который различается, с битами выше ничего сделать нельзя, биты ниже легко сделать единицами, т.к. если у нас L вида xy...z0..., а R вида xy...z1..., то очевидно, что в промежутке есть числа xy...z011...1 и xy...z100...0.

[@fshp]

«Паттернов начитался»

[@isxaker]

получается, можно хранить в trie старший бит, который различается и обновлять его при вставке очередного целого числа, а затем делать все биты ниже единицами. Правда сложность все равно будет O(n) = nlogn, но гораздо проще ).

[@freopen]

Шта???

Давайте я код напишу, чтобы было понятно: ideone.com/Po4JgL. У того, что я описал сложность — O(log n).

O(n) не равно nlogn

[@MiXei4]

O(n) = nlogn

Видимо автор всего лишь таким образом записывает фразу «Сложность алгоритма равна nlogn»

[@isxaker]

Да, вы абсолютно правильно поняли смысл моей записи. Теперь буду писать правильно )

[@isxaker]

Определенно ваше решение проще, да вдобавок еще и быстрее.

[@fshp]

Циклы явно лишние ideone.com/qKUwEk

[@freopen]

Забавно смотреть на ваши оптимизации, расположенные по соседству со считыванием через cin :)

[@fshp]

А чем его заменить? scanf? Это шило на мыло получится. А __builtin_clz на некоторых (x86) платформах разворачивается в одну инструкцию, что магическим образом превращает O(log(n)) в O(1);

[@aesamson]

Можно заменить на getchar_unlocked() для *nix или getchar() для всех остальных.
getchar_unlocked > getchar > scanf > cin, где ">" означает быстрее.
digital-madness.in/blog/2013/fast-io-in-c/

[@fshp]

Мы же число вводим, а не символ. Нам строку потом переводить в число придётся.

[@aesamson]

Дело в том, что высокоуровневые 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;
}

[@fshp]

Всё это я видел на stackoverflow, хоть источник бы указывали. Но код должен быть не только производительным, но и выразительным (иногда это даже важнее). Зачем писать по 10 утилитарных функций, зачем в цикле считать биты? Язык предоставляет для всего этого удобные, безопасные инструменты, и не стоит игнорировать их. Я там ещё и bitset использую для красивого вывода в cout. Если всё это писать самому, то решение задачки в 1 строчку превратится в очередной фреймворк. Ведь код я не усложнял, я его значительно упростил. 5 — 6 битовых операций это не так сложно.

[@aesamson]

Источник указан в комментарии выше, читайте внимательней.

• Про выразительность: выразительность это несомненно важно, но в угоду выразительности жертвовать производительность там, где важна производительность все же не стоит. Речь шла именно о производительности
  

  Забавно смотреть на ваши оптимизации, расположенные по соседству со считыванием через cin

  
  
• Про циклы:

  зачем в цикле считать биты

  Любое число — совокупность бит. В угоду производительности, там где это оправданно, а в этом случае это оправданно — можно и биты посчитать. К тому же решение весьма простое и абстракция в виде функции несомненно проста в использовании и потому эффективна.
  

• и не стоит игнорировать их

  Тезис верный, но не стоит принимать его за аксиому. Всему свое место и там где уместно использование готовых функций конечно же не стоит городить велосипеды.
  

• 5 — 6 битовых операций это не так сложно

  не понимаю тогда чем решение, предложенное мной, сложно.
  

[@bogolt]

Я бы сказал — ксорим максимальное возможное число с нулем и получаем искомое.

[@MacIn]

A должно быть больше или равно L.

[@freopen]

L не равно нулю в общем случае. Но даже для L=0 это неверно. Пусть R=4, тогда оптимальные a и b — это 3 и 4: 3^4 = 7.

[@fshp]

Xor с нулём бессмысленен. Вы получаете тоже самое число.

[@bogolt]

да затупил. спасибо всем.

[@Mercury13]

И я тут подумал — а на что он декартово всунул, когда это декартово можно хранить неявно.

Итак, моё решение. i-й бит перекрывает все биты от 0 до i−1. Потому если удастся i-й бит сделать единицей, его СТОИТ делать единицей, чхая на то, что все низшие будут нулями.

результат := 0
текБит := максБит()
пока текБит ≠ 0
  новРез := результат + текБит
  если новРез <= Б
    то результат := новРез
  текБит >>= 1

Скорость — кол-во битов в слове.

[@freopen]

Все-таки стоило прочитать статью перед написанием этого комментария…

[@Mercury13]

Да, верно, я решил не ту задачу. Не сразу заметил и переписал.

[@Mercury13]

Пардон, ошибся, решив не ту задачу.

результатА := 0
текБит := максБит()
пока текБит ≠ 0
  новРезБ := результатА + текБит
  новРезА := результатА + текБит − 1
  если новРезБ > R то 
    ничего не делать
  иначе если новРезА < L то
    результатА := новРезБ
  иначе
    результатА := новРезА
    результатБ := новРезБ
    стоп
  текБит >>= 1
результатБ := результатА // перестраховка

[@Mrrl]

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 — совпадает с переборным решением.

Или я чего-то не понял в задаче?

[@isxaker]

Добавьте небольшое пояснение вашего подхода.

[@isxaker]

Спасибо за разбор.

[@Mrrl]

Я так писать не стал, потому что, во-первых, используется конкретная разрядность, а во-вторых — 7 строчек вместо трёх.

    for(k=1;c&(c+1);k<<=1) c|=c>>k;

[@Mrrl]

Тогда для знаковых 32-битных L и R, L <= R так:

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 операций, не считая копирований.

[@oandrew]

Вот мое решение:

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.

[@Mrrl]

И что она сделает при l = -2, r = 2? Зациклится?

[@Mrrl]

Интереснее задача найти максимум и минимум для A&B, где L1 <= A <= R1, L2 <= B <= R2.