Подсчет битов в целых числах (отрицательные целые числа?)

Я действительно новичок в кодировании (начал около 1,5 недель назад), так что, надеюсь, мой вопрос здесь не является слишком отвратительным преступлением (а если это так, я прошу прощения).

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

Из того, что я узнал, у меня сложилось впечатление, что перед целым числом с отрицательным знаком просто установлен бит, как в следующем примере:

 2:  0000 0010
-2:  1000 0010

Так что в идеале моя функция должна действовать так: bit_count([negative number here]) совпадает с 1 + bit_counter([absolute value of negative number])

Но это не так.

Вот моя функция:

    int bit_count(int byte)
    {
        int bit;
        int tally;
        tally = 0;
        for (bit = 0x80; bit > 0; bit = bit >> 1)
        {
            if ((byte & bit) != 0)
                    ++tally;
        }
        return (tally);
    }

Некоторые примерные данные:

bit_count(-1) приводит к 8 bit_count(-6) приводит к 6 bit_count(-4) приводит к 6

и так далее...

У меня был друг, которому я довольно доверяю, предположил, что в зависимости от машины перед подписанным битом на самом деле было больше метаданных, которые включала моя функция подсчета битов, но я не знаю, что мне нужно. сделать, чтобы исправить это.

Спасибо


c++ signed integer bit
person ctesta01    schedule 09.01.2014    source источник
comment
Да, самый старший бит обычно представляет отрицательное число при подписании, но остальные биты также меняются.   -  person chris    schedule 09.01.2014
comment
en.wikipedia.org/wiki/Two's_complement   -  person Igor Tandetnik    schedule 09.01.2014
comment
Посмотрите дополнение до двух - переверните биты и добавьте один, чтобы изменить с +ve на -ve   -  person Ed Heal    schedule 09.01.2014

Ответы (4)


arrow_upward
2
arrow_downward

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

Другими словами, ваш код работает правильно, но ваша предпосылка о представлении отрицательных целых чисел неверна.

Механизм, используемый в целых числах со знаком, называется дополнением до двух и, по сути, означает взятие 2^n, где n — количество битов, и вычитание абсолютного значения целого числа, чтобы получить его отрицательное значение.

-2 поэтому

1111 1110

и не

1000 0010

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

person dandan78    schedule 09.01.2014
comment
... и затем обратите внимание, что не гарантируется, что платформа, на которой вы работаете, действительно использует эту кодировку (хотя это весьма вероятно). - person DevSolar; 22.06.2020

arrow_upward
0
arrow_downward

После этой строки: tally = 0; добавьте это для ваших ожидаемых результатов, поскольку отрицательные числа находятся в дополнении 2. если (байт ‹ 0) {tally=1; байт = -1 * байт;}

person user3171841    schedule 09.01.2014

arrow_upward
0
arrow_downward 

int bit_count(int num)
{
    int count = 0;
        for (unsigned int bit = 1; bit <= num && bit > 0; bit <<= 1){
           if (num & bit){ 
               count++;
           }
        }  
    return count;
}

Приведенные выше ответы также хороши и работают. И альтернативно. Этот фрагмент работал для меня.

Я использовал unsigned int, потому что он не учитывает крайний левый бит, и ожидаемый результат будет на 1 меньше.

Я хотел бы услышать предложения, если таковые имеются. Спасибо и добро пожаловать.

person Manoj Thoranala    schedule 14.06.2019

arrow_upward
-2
arrow_downward

Целое число может иметь максимум 32 бита

int n = given(say -25)
int count[32] = {0}; 
for (int i = 0; i < 32; i++) {
    if ((n >> i) & 1) {
        count[i]++;
    }
}

то мы можем повторить каждую позицию.

person arpit1714    schedule 22.06.2020
comment
Единственная гарантия, предоставляемая языком, заключается в том, что int имеет ширину 16 бит или более. Оно не обязательно должно быть кратно 8 битам. Кроме того, показанный код не подсчитывает общее количество установленных битов, он подсчитывает количество раз, когда бит position устанавливается. В целом, это не улучшение по сравнению с ответом, принятым шесть лет назад. - person DevSolar; 22.06.2020