Подсчет количества битов значения 1 в массиве - Понимание кода за ним (C) - PullRequest
Новая
       19

Подсчет количества битов значения 1 в массиве - Понимание кода за ним (C)

0 голосов
/ 23 июня 2018

Следующий код подсчитывает количество битов значения '1' в массиве 'ЬиЕ': 

long bit_count(long *arr, int size)
{
    int w,b;
    unsigned long word=0;
    long n = 0;

    for(w = 0; w<size ; w++){
        word = arr[w];
        while(word != 0){
            n += word & 1;
            word >>= 1;
        }
    }
    return n;
}

int main() {

     char buf[] = {"There is always one more!"};         //(1)
     int length = strlen(buf)>>3;                        //(2)
     long *a = (long*) (buf + length);                   //(3)
     //char * b = (char *)a; // this is a comment.       //(4)
     int len = strlen((char*)a);                         //(5)
     long total_count = bit_count((long*) buf, length);  //(6)
     *a = (*a) & (((long)1<<(len*8))-1);                 //(7)
     char *c = (char*)a;                                 //(8)
     total_count += bit_count(a,1);                      //(9)
     printf("bits number %ld\n",total_count);            //(10)

    return 0;
}

Это мое понимание кода: (пожалуйста, поправьте меня, если я ошибаюсь, я хочу понять это на самом глубоком уровне)

В строке (2) они вычисляют количество букв в буфере, которое равно 25 и эквивалентно 25 байтам. потому что размер символа составляет 1 байт. затем, сдвинув это число на 3 бита вправо, они делят его на 8, 8 определяет 8 байтов = 1 длинный тип. так сколько "длинных" содержит этот массив buf. * ​​1009 *

line (3) - 'a' указывает на значение, которое содержит приведение остатка буфера к (long *) - в строке (4) я видел, что значение b * будет "!" это точно остаток от 1 байта в массиве. но я не совсем понимаю приведение к (long *) значение, которое я получаю, отличается, если я проверяю 

long check = (long) (buf + length);

так, что именно происходит, когда я делаю - {(long*)buf} мой первый вопрос.

в строке (6) я считаю биты в первой части массива (по длинным) и в строке (9) я считаю биты в остатке.

что я не понимаю - что происходит в строке (7)?

1 Ответ

0 голосов
/ 23 июня 2018

В коде нет ничего хитрого, но это не очень хорошо.На самом деле, это очень плохо, и не из-за стиля, а потому, что он портит память. 

(2)  int length = strlen(buf)>>3;

Эта строка вычисляет все количество long объектов, которые помещаются в строку, предполагая, что longвосемь байтов (/ sizeof(long) следует использовать вместо >>3) и что int достаточно велико, чтобы вместить число (int следует использовать вместо *1010*). 

(3)  long *a = (long*) (buf + length);

Кажется, это намеревается установить a для указания фрагмента в конце строки, который недостаточно длинный, чтобы содержать другой объект long.Однако, поскольку length - это число long объектов, а buf действует как указатель на char, его арифметика неверна.Он вычисляет buf плюс length char объектов, когда намеревается вычислить buf плюс length long объектов.Следует использовать (long *) buf + length.Кроме того, предполагается, что char * с произвольным выравниванием может быть разумно преобразовано в long *, что не гарантируется стандартом C. 

(5)  int len = strlen((char*)a);

Это вычисляет количество байтов во фрагменте.Это пустая трата времени, потому что код предварительно рассчитал длину строки.Он мог бы сохранить эту длину и получить коэффициент и остаток по модулю long вместо повторного вызова strlen. 

(6)  long total_count = bit_count((long*) buf, length);

Это вычисляет количество битов, установленных в основной части буферачасть, которая обрабатывается как некоторое целое число long объектов.Как и при предыдущем преобразовании, предполагается, что char * может быть преобразовано в long *, и, кроме того, вызываемая им подпрограмма использует этот указатель для чтения long объектов из объекта, не определенного как массив long, тем самым нарушая правила псевдонимов C. 

(7)  *a = (*a) & (((long)1<<(len*8))-1);

Напомним, что a указывает на некоторое количество конечных байтов в строке.(long)1<<(len*8) перемещается немного выше этого количества байтов, предполагая, что байты составляют восемь битов (вместо 8 следует использовать CHAR_BIT).(Например, если есть два байта, это создает значение 10000 16 .) Затем вычитание одного создает битовую маску для байтов (FFFF 16 в примере).Затем *a пытается прочитать long с конца строки, после чего применение маски с & уменьшает значение, считываемое до байтов в строке.Это не только снова нарушает правила псевдонимов C, но также читает вне памяти buf, который имеет неопределенное поведение.Наконец, оператор записывает обновленное значение в *a, что еще хуже - если вам не понравилось чтение за пределами buf, теперь код пишет за пределами buf, что приводит к повреждению где-то неизвестно. 

(8)  char *c = (char*)a;

Эта строка бесполезна, поскольку c никогда не используется. 

(9)  total_count += bit_count(a,1);

Подсчитывает количество битов, установленных в long, который был обновлен в (7).

В подпрограмме bit_count мы обнаруживаем, что код считает биты один за другим.Это абсурд.Нарушение правил C о наложении псевдонимов могло бы иметь некоторое преимущество в производительности при обработке целых long объектов вместо отдельных char объектов, если используемая конкретная реализация C позволяла создавать псевдонимы с невыровненными адресами.Но этот код просто выполняет побитовую обработку;он не получает никакого преимущества от какой-либо инструкции по подсчету битов (также известной как подсчет населения) на процессоре.

Кроме того, подпрограмма bit_count признает, что для подсчета битов следует использовать unsigned long, поскольку он определяет word как unsigned long.Но он не может распознать, что должен был использовать unsigned long повсюду, так как long может иметь представление прерывания, которое приведет к сбою кода.

Он также определяет b, даже не используя его.

...