Как-то давненько хотел написать пост на эту тему, и вот сегодня увидел мега-баннер от Global Logic:
Собственно теперь повод есть( сори за баян если что ).
ИМХО задача бесполезная, но при этом популярная в собеседованиях С/С++. Решается она не сложно - через деление на 2( я решил не рассматривать этот случай ), либо сдвигом, либо масками. Сдвиг – очевидно более простое решение, и его обычно подразумевают. Вот пример реализации сдвигом:
// Решение сдвигом
int runtime_bits_count( unsigned int n )
{
unsigned int c = 0;
for ( ; n; n >>= 1 ) n & 1 && ++c;
return c;
}
Также нужно заметить, что математики уже давно всё посчитали, и для каждого типа целого есть некий набор хитрых манипуляций и масок. Вот пример для 32-битного целого:
// Более быстрый алгоритм с масками
// Генри Уоррен мл. Алгоритмические трюки для програмистов.
// Глава 5 Подсчет битов, листинг 5.1
unsigned int runtime_fast_bits_count( unsigned int n )
{
n = n - ( ( n >> 1 ) & 0x55555555 );
n = ( n & 0x33333333 ) + ( ( n >> 2 ) & 0x33333333 );
n = ( n + ( n >> 4 ) ) & 0x0F0F0F0F;
n = n + ( n >> 8 );
n = n + ( n >> 16 );
return n & 0x0000003F;
}
Я не зря написал в названии функций ‘runtime’, ведь функция считает установленные биты только во время выполнения. Но если входящий параметр константа/дефайн/число – то можно было б посчитать всё во время компиляции. Вот пример решения для однобайтного целого на Си:
// Compile-time bits_count в стиле С
#define bits_count( n ) \
( n & 0x01 ? 1 : 0 ) + ( n & 0x02 ? 1 : 0 ) + \
( n & 0x04 ? 1 : 0 ) + ( n & 0x08 ? 1 : 0 ) + \
( n & 0x10 ? 1 : 0 ) + ( n & 0x20 ? 1 : 0 ) + \
( n & 0x40 ? 1 : 0 ) + ( n & 0x80 ? 1 : 0 )
const unsigned char b = 120;
int res = bits_count( b ); // compile-time
Для однобайтного на С++:
// Тот же подход но в стиле С++
template < unsigned char n >
struct bits_count
{
enum
{
RES = ( n & 0x01 ? 1 : 0 ) + ( n & 0x02 ? 1 : 0 ) +
( n & 0x04 ? 1 : 0 ) + ( n & 0x08 ? 1 : 0 ) +
( n & 0x10 ? 1 : 0 ) + ( n & 0x20 ? 1 : 0 ) +
( n & 0x40 ? 1 : 0 ) + ( n & 0x80 ? 1 : 0 )
};
};
const unsigned char b = 120;
int res = bits_count < b >::RES; // compile-time
Круто. А теперь еще немножко и получим менее зависимую от ширины типа реализацию:
template < unsigned int x >
struct bitscount
{
static const unsigned int n = bitscount < x / 2 >::n + x % 2;
};
template < >
struct bitscount < 0 >
{
static const unsigned int n = 0;
};
#define dec2bin( x ) bitscount < ( x ) >::n
int _tmain( int argc, _TCHAR* argv[] )
{
const int b = 60000; // 32 bit!
size_t t = dec2bin( b ); // in compile-time
return 0;
}
Теперь остаеться написать реализацию для n-байтного целого, где если это константа – вычисление должно быть во время компиляции. Иногда говорят: «надо заставить компилятор за нас думать», оно вроде сейчас так и получается, но думаю всё равно я, а он компилит). Думал, думал – и не придумал). Зато нашел полезную вещь которая детектит константность во время компиляции:
struct check_const
{
struct Temp { Temp( int x ) { } };
static char chk2( void* ) { return 0; }
static int chk2( Temp ) { return 0; }
};
#define is_const( t ) \
( sizeof( check_const::chk2( 0 + !!( t ) ) ) != sizeof( check_const::chk2( 0 + !( t ) ) ) )
