Я пытаюсь найти положение двух 1 в 64-битном номере. В этом случае они находятся на 0-й и 63-й позиции. Код здесь возвращает 0 и 32, что только половина права. Почему это не работает?
#include<stdio.h>
void main()
{
unsigned long long number=576460752303423489;
int i;
for (i=0; i<64; i++)
{
if ((number & (1 << i))==1)
{
printf("%d ",i);
}
}
}
В строке есть две ошибки
if ((number & (1 << i))==1)
который должен читать
if (number & (1ull << i))
Изменение 1 на 1ull означает, что сдвиг влево выполняется по значению типа unsigned long long, а не int, и поэтому битовая маска может фактически достигать позиций с 32 по 63. Удаление сравнения с 1 является потому что результат number & mask (где mask имеет только один бит) либо mask, либо 0, а mask равен только 1, когда я равно 0.
Однако, когда я делаю это изменение, вывод для меня - 0 59, который все еще не тот, который вы ожидали. Оставшаяся проблема заключается в том, что 576460752303423489 (десятичный) = 0800 0000 0000 0001 (шестнадцатеричный). 0 59 - правильный вывод для этого числа. Требуемое число: 9223372036854775809 (десятичный) = 8000 0000 0000 0001 (hex).
Кстати, main требуется для возврата int, а не void, и для него требуется явное return 0; в качестве последнего действия (если только вы не делаете что-то более сложное с кодом возврата). Да, C99 позволяет вам опустить это. Сделайте это в любом случае.
Потому что (1 << i) - это 32-разрядное значение int на платформе, которую вы компилируете и запускаете. Затем он получает расширенный знак до 64 бит для операции & со значением number, в результате чего бит 31 дублируется в биты с 32 по 63.
Кроме того, вы сравниваете результат & с 1, что неверно. Он не будет равен 0, если бит установлен, но не будет 1.
Смещение 32-битного int на 32 составляет undefined.
Кроме того, ваш номер ввода неверен. Биты устанавливаются в положениях 0 и 59 (или 1 и 60, если вы предпочитаете считать, начиная с 1).
Исправление состоит в том, чтобы использовать (1ull < i) или иначе, чтобы сдвинуть исходное значение вправо и & на 1 (вместо сдвига слева). И, конечно, если вы сделаете left-shift 1 и & с исходным значением, результат не будет равен 1 (кроме бит 0), поэтому вам нужно сравнить != 0, а не == 1.
#include<stdio.h>
int main()
{
unsigned long long number = 576460752303423489;
int i;
for (i=0; i<64; i++)
{
if ((number & (1ULL << i))) //here
{
printf("%d ",i);
}
}
}
Сначала нужно использовать 1ULL для представления константы unsigned long long. Второй в инструкции if, что вы имеете в виду, это не сравнивать с 1, это будет верно только для самого правого бита.
Выход: 0 59
Это правильно, потому что 576460752303423489 равно 0x800000000000001
В первую очередь проблему можно было бы избежать, приняв методологию применения оператора >> к переменной вместо литерала:
if ((variable >> other_variable) & 1)
...
Я знаю, что у вопроса есть некоторое время и несколько правильных ответов, в то время как мой комментарий должен быть, но слишком длинный для него. Я советую вам инкапсулировать логику проверки битов в макрос и не использовать 64 числа напрямую, а скорее вычислить его. Посмотрите здесь для довольно полного источника хакерских манипуляций.
#include<stdio.h>
#include<limits.h>
#define CHECK_BIT(var,pos) ((var) & (1ULL<<(pos)))
int main(void)
{
unsigned long long number=576460752303423489;
int pos=sizeof(unsigned long long)*CHAR_BIT-1;
while((pos--)>=0) {
if(CHECK_BIT(number,pos))
printf("%d ",pos);
}
return(0);
}
Вместо того, чтобы прибегать к манипуляции с битами, можно использовать средства компилятора для выполнения задач анализа бит наиболее эффективным образом (во многих случаях используется только одна команда ЦП).
Например, gcc и clang предоставляют такие удобные подпрограммы:
__builtin_popcountll() - number of bits set in the 64b value
__builtin_clzll() - number of leading zeroes in the 64b value
__builtin_ctzll() - number of trailing zeroes in the 64b value
__builtin_ffsll() - bit index of least significant set bit in the 64b value
Другие компиляторы имеют схожие механизмы.