Armenian Knowledge Base  

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

Reply
 
LinkBack Thread Tools
Old 29.01.2014, 22:24   #1
Untouchable misanthrope
 
AvDav's Avatar
 
Join Date: 07 2004
Location: Pure thoughts
Age: 36
Posts: 3,408
Downloads: 22
Uploads: 0
Reputation: 222 | 3
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 With Quote
Reply

Thread Tools

Similar Threads
Thread Thread Starter Forum Replies Last Post
number theory spx123 Science and Education 1 16.06.2006 21: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 15:53


На правах рекламы:
реклама

All times are GMT. The time now is 19:47.


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