Go Back   Armenian Knowledge Base > Technical sections > Languages, Compilers, Interpreters

Reply
 
Thread Tools

Counting set bits in a binary number
Old 29.01.2014, 21:24   #1
Ego coder
 
AvDav's Avatar
 
Join Date: 07 2004
Location: Yerevan, Armenia
Age: 44
Posts: 3,738
Rep Power: 5
Default Counting set bits in a binary number

Задача об оптимальном подчсёте единичных битов в целочисленном типе. Моя реализация основана на использовании малой дополнительной памяти, из-за чего скорость вычисления пропорцианалься Օ(1). Это стандартный алгоритм, применяемый во многих известных мне библиотеках, просто я сам до него допёр когда столкнулся с такой задачей по работе.

Code:
#include <iostream>
     
struct byte {
    static const unsigned char ones_in_nibble[];
    unsigned char low: 4;
    unsigned char hi: 4;
    inline unsigned char getones() const {return ones_in_nibble[low] + ones_in_nibble[hi];}
};
const unsigned char byte::ones_in_nibble[] = {0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4};
     
unsigned char getBitCount(unsigned int n) {
    byte* bytes = (byte*)&n;
    return bytes[3].getones() + bytes[2].getones() + bytes[1].getones() + bytes[0].getones();
}
void binOutput(unsigned int n) {
    for(int i = ((sizeof(n) << 3) - 1); i >= 0; std::cout << ((n >> i--) & 1));
}
     
int main() {
    const unsigned int num = 0xaabbccdd;
    std::cout << "The binary number (";
    binOutput(num);
    std::cout << ") has in total of " << (int)getBitCount(num) << " set bits.";
    return 0;
}
P.S. Пытаюсь писать наиболее самокоментируемый код, во избежание тривиальных
комментариев.
__________________
Каждый сам кузнец своего счастья, и несчастья тоже.
Reply



Similar Threads
Thread Thread Starter Forum Replies Last Post
number theory spx123 Science and Education 1 16.06.2006 20:52
LED Binary Clock acid Fun 3 26.03.2004 06:24
Binary Division: DaNYer Algorithms 5 10.12.2003 15:42
Binary Addition DaNYer Algorithms 13 27.11.2003 07:53
2 Lines for 1 number petar General 2 08.09.2002 14:53


Реклама:
реклама
Buy text link .

All times are GMT. The time now is 01:41.
Top

Powered by vBulletin® Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.