Количество единиц в двоичных представлениях двоичных чисел в диапазоне

Question

Эта проблема взята из Codesprint 2011 (http://csfall11.interviewstreet.com/):

Одной из основ информатики является знание того, как числа представлены в дополнении 2. Представьте, что вы записываете все числа между A и B включительно в представлении дополнения 2, используя 32 бита. Сколько всего 1 вы запишите? Входные данные: Первая строка содержит количество тестов T (<1000). Каждая из следующих строк T содержит два целых числа A и B. Выход: Выведите T строк, по одной для каждого теста. Ограничения: -2 ^ 31 <= A <= B <= 2 ^ 31 - 1 </p>

Пример ввода: 3 -2 0 -3 4 -1 4 Пример вывода: 63 99 37

Пояснение: Для первого случая -2 содержит 31 1, за которым следует 0, -1 содержит 32 1 и 0 содержит 0 1. Таким образом, всего 63. Для второго случая ответом является 31 + 31 + 32 + 0 + 1 + 1 + 2 + 1 = 99

Я понимаю, что вы можете использовать тот факт, что число 1 в -X равно числу 0 в дополнении (-X) = X-1, чтобы ускорить поиск. В решении утверждается, что для генерации ответа существует рекуррентное отношение O (log X), но я его не понимаю. Код решения можно посмотреть здесь: https://gist.github.com/1285119

Буду признателен, если кто-нибудь сможет объяснить, как получается это отношение!

Answer 1

Ну, это не , что сложно ...

Функция с одним аргументом solve(int a) является ключом.Он короткий, поэтому я вырезал и вставлял его здесь:

long long solve(int a)
{
 if(a == 0) return 0 ;
 if(a % 2 == 0) return solve(a - 1) + __builtin_popcount(a) ;
 return ((long long)a + 1) / 2 + 2 * solve(a / 2) ;
}

Он работает только для неотрицательных значений a и подсчитывает число 1 бит во всех целых числах от 0 до a включительно.

Функция имеет три случая:

a == 0 -> возвращает 0. Очевидно.

a even -> возвращает число 1 бит в a plus solve(a-1).Также довольно очевидно.

Последний случай интересный.Итак, как мы посчитаем число 1 бит от 0 до нечетного числа a?

Рассмотрим все целые числа от 0 до a и разделим их на две группы: четные ишансы.Например, если a равно 5, у вас есть две группы (в двоичном формате):

000  (aka. 0)
010  (aka. 2)
100  (aka. 4)

и

001  (aka 1)
011  (aka 3)
101  (aka 5)

Обратите внимание, что эти две группы должны иметь одинаковый размер (посколькуa нечетно и диапазон включительно).Чтобы подсчитать, сколько 1 битов имеется в каждой группе, сначала подсчитайте все биты, кроме последних, а затем подсчитайте последние биты.

Все биты, кроме последних, выглядят так:... и это выглядит так для обеих групп.Число 1 бит здесь просто solve(a/2).(В этом примере это число 1 битов от 0 до 2. Также напомним, что целочисленное деление в раундах C / C ++ вниз .)

Последний бит равен нулю для каждогочисло в первой группе и по одному на каждое число во второй группе, поэтому эти последние биты вносят (a+1)/2 один бит в общую сумму.

Таким образом, третий случай рекурсии - (a+1)/2 + 2*solve(a/2) с соответствующими приведениямиlong long для обработки случая, когда a равно INT_MAX (и, таким образом, a+1 переполняется).

Это решение O (log N).Чтобы обобщить его до solve(a,b), вы просто вычисляете solve(b) - solve(a) плюс соответствующую логику для беспокойства об отрицательных числах.Вот что делает два аргумента solve(int a, int b).

Answer 2

Приведите массив в последовательность целых чисел.Затем для каждого целого числа выполните:

int NumberOfSetBits(int i)
{
   i = i - ((i >> 1) & 0x55555555);
   i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
   return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}

Также это переносимо, в отличие от __builtin_popcount

См. Здесь: Как посчитать количество установленных бит в 32-битном целом?1007 *

Answer 3

когда положительное, лучшее объяснение уже было опубликовано.

Если a отрицательно, то в 32-битной системе каждое отрицательное число от a до нуля будет иметь 32 1-битных числа меньше числа бит в диапазоне от 0 до двоичного представления положительного a.

Итак, лучше,

long long solve(int a) {
    if (a >= 0){
        if (a == 0) return 0;
        else if ((a %2) == 0) return solve(a - 1) + noOfSetBits(a);
        else return (2 * solve( a / 2)) + ((long long)a + 1) / 2;
    }else {
        a++;
        return ((long long)(-a) + 1) * 32 - solve(-a);
    }
}

Answer 4

В следующем коде битовая сумма x определяется как число 1 бит в дополнительном представлении чисел от 0 до x (включительно), где Integer.MIN_VALUE <= x <= Integer.MAX_VALUE. </p>

Например:

bitsum(0) is 0   
bitsum(1) is 1   
bitsum(2) is 1   
bitsum(3) is 4

.. и т.д.

10987654321098765432109876543210 i % 10 for 0 <= i <= 31
00000000000000000000000000000000 0
00000000000000000000000000000001 1
00000000000000000000000000000010 2
00000000000000000000000000000011 3
00000000000000000000000000000100 4
00000000000000000000000000000101 ...
00000000000000000000000000000110
00000000000000000000000000000111 (2^i)-1
00000000000000000000000000001000  2^i
00000000000000000000000000001001 (2^i)+1 
00000000000000000000000000001010 ...
00000000000000000000000000001011 x, 011 = x & (2^i)-1 = 3
00000000000000000000000000001100
00000000000000000000000000001101
00000000000000000000000000001110
00000000000000000000000000001111
00000000000000000000000000010000
00000000000000000000000000010001
00000000000000000000000000010010 18
...
01111111111111111111111111111111 Integer.MAX_VALUE

Формула битовой суммы:

bitsum(x) = bitsum((2^i)-1) + 1 + x - 2^i + bitsum(x & (2^i)-1 )

Обратите внимание, что x - 2 ^ i = x & (2 ^ i) -1

Отрицательные числа обрабатываются немного иначе, чем положительные числа. В этом случае число нулей вычитается из общего числа битов:

Integer.MIN_VALUE <= x < -1
Total number of bits: 32 * -x.

Число нулей в отрицательном числе x равно числу нулей в -x - 1.

public class TwosComplement {
    //t[i] is the bitsum of (2^i)-1 for i in 0 to 31.
    private static long[] t = new long[32];
    static {
        t[0] = 0;
        t[1] = 1;
        int p = 2;
        for (int i = 2; i < 32; i++) {
            t[i] = 2*t[i-1] + p;
            p = p << 1;
        }
    }

    //count the bits between x and y inclusive
    public static long bitsum(int x, int y) {
        if (y > x && x > 0) {
            return bitsum(y) - bitsum(x-1);
        }
        else if (y >= 0 && x == 0) {
            return bitsum(y);
        }
        else if (y == x) {
            return Integer.bitCount(y);
        }
        else if (x < 0 && y == 0) {
            return bitsum(x);
        } else if (x < 0 && x < y && y < 0 ) {
            return bitsum(x) - bitsum(y+1);
        } else if (x < 0 && x < y && 0 < y) {
            return bitsum(x) + bitsum(y);
        }
        throw new RuntimeException(x + " " + y);
    }

    //count the bits between 0 and x
    public static long bitsum(int x) {
        if (x == 0) return 0;
        if (x < 0) {
            if (x == -1) {
                return 32;
            } else {
                long y = -(long)x;
                return 32 * y - bitsum((int)(y - 1));
            }
        } else {
            int n = x;
            int sum = 0;     //x & (2^i)-1
            int j = 0;
            int i = 1;       //i = 2^j
            int lsb = n & 1; //least significant bit
            n = n >>> 1;
            while (n != 0) {
                sum += lsb * i;
                lsb = n & 1;
                n = n >>> 1;
                i = i << 1;
                j++;
            }
            long tot = t[j] + 1 + sum + bitsum(sum);
            return tot;
        }
    }
}