Печать битов длинным длинным числом (C++)
Я хочу напечатать все биты длинного длинного числа. Когда я делаю это в main (), все в порядке, но в функции printBits () (где код такой же) есть лишняя 1 на 32-м бите.
Код:
#include <iostream>
void printBits(long long number)
{
std::cout<<number<<" -> ";
for (char i=63; i>=0; --i)
{
std::cout<<(bool)(number&(1<<i));
}
std::cout<<std::endl;
}
int main()
{
long long number=1;
std::cout<<number<<" -> ";
for (char i=63; i>=0; --i)
{
std::cout<<(bool)(number&(1<<i));
}
std::cout<<std::endl;
printBits(number);
return 0;
}
Результат:
1 -> 0000000000000000000000000000000000000000000000000000000000000001
1 -> 0000000000000000000000000000000100000000000000000000000000000001
Process returned 0 (0x0) execution time : 0.012 s
Press any key to continue.
Подтверждено - использование ((long long) 1) вместо 1 устраняет проблему.
Помимо исправления с 1ll, почему результат в main() отличается от результата в printBits()?
std::cout << std::bitset<64>(number) << std::endl;
Ответы 3
Литерал 1 по умолчанию является целым числом. Забросьте на долгое время, чтобы решить проблему.
std::cout<<(bool)(number&(((long long)1)<<i));
(bool)(number&(1ll << i)); хватило бы. Суффикс ll обозначает long long.
Этот ответ можно улучшить, объяснив, почему использование int не работает.
@GillBates Вы уверены, что изменили оба способа использования 1 << i?
@ FrançoisAndrieux Да, это исправило.
Возможно, стоит объяснить в своем ответе, что 1 - это целое число, и поэтому (1 << i) - это UB согласно стандарту, когда i равно 32 или больше ([expr.shift] «Поведение не определено, если правый операнд отрицательный или больше или равен длине в битах продвинутого левого операнда»)
Как показывает ответ Cpp plus 1, вам необходимо изменить литерал (по умолчанию int) 1 на длинный длинный литерал 1LL или 1ll.
Однако вам может быть лучше использовать std::bitset вместо вашей функции:
#include <bitset>
long long number = 1; // int number = 1; also works
std::bitset<64> bits(number);
std::cout << number << " -> " << bits << std::endl;
дает:
1 -> 0000000000000000000000000000000000000000000000000000000000000001
Причина, по которой вы получаете этот вывод, заключается в том, что для конкретного оборудования / компилятора, которое вы используете:
a << x работает следующим образом: a << (x mod (8 * sizeof(a)). Поэтому для 1 вы получите
1 << (x mod 32). Это означает, что на 32-й итерации цикла:
std::cout << (bool)(number & (1 << 32));
// becomes
std::cout << (bool)(number & (1 << 0));
// printing '1'
Я не верю, что ваше объяснение правильное, поскольку один и тот же код дает два разных результата. Если бы то, что вы сказали, было правдой, обе петли дали бы то же самое.
@NathanOliver прав. На самом деле спрашивающий вызвал неопределенное поведение.
@jxh Конечно, но нигде в этом ответе не говорится, что это неопределенное поведение, а определение поведения звучит так, как будто оно всегда будет работать таким образом.
Причина разных результатов в том, что компилятор (здесь clang 6.0) может создавать разный код в основной функции и в printBits.
В main известно, что number всегда равен 1 и никогда не меняется. Также «очевидно», что это может произвести только один 1 на выходе. Итак, оптимизатор переписывает цикл как:
for (char i=64; i > 0; --i)
{
std::cout<< (i == 1 ? 1 : 0);
}
Смотри, мама, никаких смен!
Сборка выглядит так
012B13CC mov bl,40h ; i = 40h = 64
012B13CE xchg ax,ax ; nop to align the loop
main+30h:
012B13D0 xor eax,eax
012B13D2 cmp bl,1 ; i == 1?
012B13D5 mov ecx,esi
012B13D7 sete al
012B13DA push eax
012B13DB call edi ; edi -> operator<<
012B13DD dec bl
012B13DF jg main+30h (012B13D0h)
В printBits он не может оптимизироваться таким образом, так как функция может быть вызвана из другого места. Вот он и выполняет сдвиг (с ошибочным результатом).
Интересно, что не удалось оптимизировать константу после встраивания функции.
GCC тоже это делает: tio.run/…
Я подозреваю, что проблема связана с тем, что
1 << iявляетсяint, а неlong long.