Почему этот битовый код не проходит свои тесты? - PullRequest
Новая
       9

Почему этот битовый код не проходит свои тесты?

0 голосов
/ 18 сентября 2018

Я сейчас занимаюсь в лаборатории bit.c и делаю функцию bitCount, я думаю, что она идеальна, но не может пройти тест.Я не знаю почему. 

int bitCount(int x) {
    unsigned int a = 0x01010101;
    int b;
    int result = 0;
    result += a&x;
    result += a&(x>>1);
    result += a&(x>>2);
    result += a&(x>>3);
    result += a&(x>>4);
    result += a&(x>>5);
    result += a&(x>>6);
    result += a&(x>>7);
    b = result + result >> 8;
    b = b + result >> 16;
    b = b + result >> 24;
    return b&0xff;
}

1 Ответ

0 голосов
/ 20 сентября 2018

Вы суммируете неправильные биты, потому что + имеет более высокий приоритет, чем >>, в этих строках: 

b = result + result >> 8;
b = b + result >> 16;
b = b + result >> 24;

Предположим, что result == 0x01020304:

  • Выражение result + result >> 8 приведет к 0x01020304 + 0x01020304 >> 8, затем 0x02040608 >> 8 и, наконец, 0x020406.
  • Выражение b = b + result >> 16 приведет к 0x020406 + 0x01020304 >> 16, затем 0x0104070A >> 16 и, наконец, 0x010407.
  • Выражение b = b + result >> 24 приведет к 0x010407 + 0x01020304 >> 24, затем 0x0103070B >> 24 и, наконец, 0x010307.
  • В конце выражения b&0xff приводит к 0x07. Не результат 0x0A или 10, которые мы ожидали.

Таким образом, вы должны:

  1. Убедитесь, что сдвиг сделан перед сложением. Используйте скобки ().
  2. Маскируйте ненужные биты с помощью & 0xFF. Обратите внимание, что это не является строго необходимым, поскольку есть b&0xff, но, на мой взгляд, это делает намерение более ясным.
* * Пример тысячу сорок четыре: * * 1045 
b = (result & 0xFF) + (result >> 8 & 0xFF);
b = b + (result >> 16 & 0xFF);
b = b + (result >> 24 & 0xFF);
...