Функционирование побитового и

Question

Этот вопрос был задан в интервью, кто-то может сказать, что делает следующий код? Он выдает 15 для 150, 3 для 160, 15 для 15. Какую математическую операцию он выполняет над 'n'.

int foo(int n) 
{
    int t,count=0;
    t=n;
    while(n)
    {
        count=count+1;
        n=(n-1)&t;
    }
    return count;
}

Answer 1

Кажется, рассчитать число max(n**2-1, 0)где n - число 1 биты в двоичном представлении числа:

    0     0 0b0  
    1     1 0b1  
    2     1 0b10 
    3     3 0b11 
    4     1 0b100
    5     3 0b101
    6     3 0b110
    7     7 0b111
    8     1 0b1000
    9     3 0b1001
   10     3 0b1010
   11     7 0b1011
   12     3 0b1100
   13     7 0b1101
   14     7 0b1110
   15    15 0b1111
   16     1 0b10000
   17     3 0b10001
   18     3 0b10010
   19     7 0b10011
   20     3 0b10100
   21     7 0b10101
   22     7 0b10110
   23    15 0b10111
   24     3 0b11000
   25     7 0b11001
   26     7 0b11010
   27    15 0b11011
   28     7 0b11100
   29    15 0b11101
   30    15 0b11110
   31    31 0b11111
   32     1 0b100000
   33     3 0b100001
   34     3 0b100010
   35     7 0b100011
   36     3 0b100100
   37     7 0b100101
   38     7 0b100110
   39    15 0b100111
   40     3 0b101000
   41     7 0b101001
   42     7 0b101010
   43    15 0b101011
   44     7 0b101100
   45    15 0b101101
   46    15 0b101110
   47    31 0b101111
   48     3 0b110000
   49     7 0b110001
   50     7 0b110010
   51    15 0b110011
   52     7 0b110100
   53    15 0b110101
   54    15 0b110110
   55    31 0b110111
   56     7 0b111000
   57    15 0b111001
   58    15 0b111010
   59    31 0b111011
   60    15 0b111100
   61    31 0b111101
   62    31 0b111110
   63    63 0b111111
   64     1 0b1000000
   65     3 0b1000001
   66     3 0b1000010
   67     7 0b1000011
   68     3 0b1000100
   69     7 0b1000101
   70     7 0b1000110
   71    15 0b1000111
   72     3 0b1001000
   73     7 0b1001001
   74     7 0b1001010
   75    15 0b1001011
   76     7 0b1001100
   77    15 0b1001101
   78    15 0b1001110
   79    31 0b1001111
   80     3 0b1010000
   81     7 0b1010001
   82     7 0b1010010
   83    15 0b1010011
   84     7 0b1010100
   85    15 0b1010101
   86    15 0b1010110
   87    31 0b1010111
   88     7 0b1011000
   89    15 0b1011001
   90    15 0b1011010
   91    31 0b1011011
   92    15 0b1011100
   93    31 0b1011101
   94    31 0b1011110
   95    63 0b1011111
   96     3 0b1100000
   97     7 0b1100001
   98     7 0b1100010
   99    15 0b1100011

Answer 2

Проще узнать "математическую операцию", когда функция меняется на рекурсивную:

int foo(int n, int t) 
{
    if( n )
        return foo( (n-1) & t ) + 1
    else
        return 0; 
}

Итак, формула:

F(0,t) = 0
F(n,t) = F( (n-1) & t, t ) + 1

foo(n) = F(n,n)

Я понятия не имею, это известная формула подсчета чего-либо или нет.

Вы можете найти ответ от http://math.stackexchange.com/

Answer 3

Этот метод известен как способ Брайана Кернигана подсчитывать биты:

unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v
for (c = 0; v; c++)
{
  v &= v - 1; // clear the least significant bit set
}

Метод Брайана Кернигана проходит столько итераций, сколько есть установленных битов. Так что если у нас есть 32-битное слово с установленным старшим битом, оно будет проходить только один раз в цикле.

Опубликовано в 1988 году, язык программирования Си 2-е изд. (Брайан В. Керниган и Деннис М. Ричи) упоминает об этом в упражнении 2-9. 19 апреля 2006 г. Дон Кнут указал мне на то, что этот метод "впервые был опубликован Питером Вегнером в CACM 3 (1960), 322. (Также был открыт независимо Дерриком Лемером и опубликован в 1964 г. в книге, отредактированной Беккенбахом)".