`

bit count in c (1)

    博客分类:
  • c
c 
阅读更多

=============================运行结果

4296000 -> 10000011000110101000000

  a1_bitcount: num of 1=7, time=782 ms

  a2_bitcount: num of 1=7, time=265 ms

  a3_bitcount: num of 1=7, time=938 ms

  a4a_bitcount: num of 1=7, time=78 ms

  a4b_bitcount: num of 1=7, time=62 ms

=============================运行结果end

 

Playing

Playing

 

=============================文件列表

src/main.c

src/lib/bitCount.c

src/lib/showBinary.c

src/lib/ut.h

src/lib/pre16.h

src/lib/pre8.h

=============================代码

src/main.c

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "lib/ut.h"

typedef int (*FunctionCallback)(unsigned int);
FunctionCallback functions[] = { &a1_bitcount, &a2_bitcount, &a3_bitcount
    , &a4a_bitcount, &a4b_bitcount};
char * names[]={"a1_bitcount", "a2_bitcount", "a3_bitcount"
    , "a4a_bitcount", "a4b_bitcount"};

void testFun(int fIdx, unsigned int num) {
  int rlt;
  long i;
  clock_t start = clock();
  //注意,这里多运行n次,只是为了测试时间方便。
  for (i = 0; i < 10000000; i++) {
    rlt = functions[fIdx](num);
  }
  double time = ((double) clock() - start); // / CLOCKS_PER_SEC
  printf("  %s: num of 1=%d, time=%.0f ms\n", names[fIdx], rlt, time);
}

int main(void) {
  //unsigned int num = 4294967295;
  unsigned int num = 4296000;
  //unsigned int num = -1;
  int funSize = sizeof(functions) / sizeof(FunctionCallback);
  showBinary(num);
  int i;
  for(i=0;i<funSize;i++){
    testFun(i, num);
  }
  return EXIT_SUCCESS;
}

src/lib/bitCount.c

/*
 * bitCount.c
 * http://gurmeet.net/puzzles/fast-bit-counting-routines/
 */
#include "ut.h"
#include "pre8.h"
#include "pre16.h"

//1. Iterated Count
int a1_bitcount(unsigned int n) {
  int count = 0;
  while (n) {
    count += n & 0x1u;
    n >>= 1;
  }
  return count;
}

//2. Sparse Ones
int a2_bitcount(unsigned int n) {
  int count = 0;
  while (n) {
    count++;
    n &= (n - 1);
  }
  return count;
}

//3. Dense Ones
int a3_bitcount(unsigned int n) {
  int count = 8 * sizeof(int);
  n ^= (unsigned int) -1;
  while (n) {
    count--;
    n &= (n - 1);
  }
  return count;
}

//4a. Precompute-8bit
int a4a_bitcount(unsigned int n) {
  // works only for 32-bit ints
  return bits_in_char[n & 0xffu]
       + bits_in_char[(n >> 8) & 0xffu]
       + bits_in_char[(n >> 16) & 0xffu]
       + bits_in_char[(n >> 24) & 0xffu];
}

//4b. Precompute-16bit
int a4b_bitcount (unsigned int n)  {
   // works only for 32-bit ints
   return bits_in_16bits [n         & 0xffffu]
       +  bits_in_16bits [(n >> 16) & 0xffffu] ;
}
 

src/lib/showBinary.c

/*
 *  http://stackoverflow.com/questions/699968/display-the-binary-representation-of-a-number-in-c
 */
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "ut.h"
#define SZ 32

/* Create a string of binary digits based on the input value.
 Input:
 val:  value to convert.
 buff: buffer to write to must be >= sz+1 chars.
 sz:   size of buffer.
 Returns address of string or NULL if not enough space provided.
 */
static char *binrep(unsigned int val, char *buff, int sz) {
  char *pbuff = buff;

  /* Must be able to store one character at least. */
  if (sz < 1)
    return NULL;

  /* Special case for zero to ensure some output. */
  if (val == 0) {
    *pbuff++ = '0';
    *pbuff = '\0';
    return buff;
  }

  /* Work from the end of the buffer back. */
  pbuff += sz;
  *pbuff-- = '\0';

  /* For each bit (going backwards) store character. */
  while (val != 0) {
    if (sz-- == 0)
      return NULL;
    *pbuff-- = ((val & 1) == 1) ? '1' : '0';

    /* Get next bit. */
    val >>= 1;
  }
  return pbuff + 1;
}

void showBinary(unsigned int num) {
  char buff[SZ + 1];
  printf("%d -> %s\n", num, binrep(num, buff, SZ));
}

int main_showBinary(void) {
  char *argv[] = { "", "4" };
  int argc = sizeof(argv) / sizeof(char *);
  int i;
  int n;
  for (i = 1; i < argc; i++) {
    n = atoi(argv[i]);
    showBinary(n);
  }
  return 0;
}
 

src/lib/ut.h

 

#ifndef H1_H_
#define H1_H_

// here goes all the code
void showBinary(unsigned int num);
int a1_bitcount(unsigned int n);
int a2_bitcount(unsigned int n);
int a3_bitcount(unsigned int n);
int a4a_bitcount(unsigned int n);
int a4b_bitcount(unsigned int n);

#endif /* H1_H_ */
 

src/lib/pre8.h

 

#ifndef PRE8_H_
#define PRE8_H_

static int bits_in_char [256]={
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5
, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6
, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6
, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7
, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6
, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7
, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7
, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
};

#endif /* PRE8_H_ */
 

src/lib/pre8.h

src/lib/pre16.h

生成上述二文件的代码在bit count in c (2) -- precompute

 

  • 大小: 15.3 KB
分享到:
评论
发表评论

文章已被作者锁定,不允许评论。

相关推荐

    Introduction to 64Bit Windows Assembly

    One chapter covers how to efficiently count the 1 bits in an array with the most efficient version using the recently-introduced popcnt instruction. Another chapter covers using SSE instructions to ...

    stm I2C中断程序

    // sr1_i2c__state[5]=i2c_state&((u8)I2C_SR1_BIT6); sr1_analysis_int_resource[6]=i2c_sr1&I2C_SR1_RXNE; sr1_analysis_int_resource[7]=i2c_sr1&I2C_SR1_TXE; //analysis interrupt resource in i2c-&gt;...

    IMX6Q-HDMI-VGA-LVDS-双网口交换机显示控制板PDF原理图PCB+AD集成封装文件.zip

    Library Component Count : 52 Name Description ---------------------------------------------------------------------------------------------------- 0.1uF/16V C 0.1uF X7R 16V 10﹪ 0402 0.1uF/50V C 0.1...

    BURNINTEST--硬件检测工具

    support only, 32-bit BurnInTest restricted to 32-bit Windows and BurnInTest run as administrator. Release 5.3 build 1034 WIN32 release 3 October 2008 - Correction to setting the CD burn test drive...

    用C语言编写的时钟程序

    sbit inc=P1^5; sbit dec=P1^6; sbit ok=P1^7; sbit light=P2^0;`:定义了一系列控制按钮和背光控制引脚。 - 各种位变量如 `bit first_flag=1, second_flag, third_flag, playmusic, light_flag1=1, light_flag;` ...

    2011年全国电子设计大赛c题智能小车-沿内线循迹源代码。.txt

    #include&lt;reg52.h&gt; #include&lt;delay.h&gt; #define uchar unsigned char #define uint unsigned int #define gaowei0 (65536-500)/256 #define diwei0 (65536-500)%256 bit a=0,b=0,c=0,beyound_flag=0,kaishi=1,...

    基于C语言的洗衣机程序

    - `#define` 语句用于定义常量,例如 `waterin P1_6` 表示水进端口映射到P1.6引脚,`waterout P1_5` 表示水出端口映射到P1.5引脚,`swim P1_7` 表示洗涤电机控制端口映射到P1.7引脚。 2. **变量声明**: - `bit ...

    单片机程序设计 电子钟程序

    INC A MOV FLAG_1S,A ;1S取反标志取反,等待下一秒 SETB C MOV A,CLOSE_BIT RLC A MOV CLOSE_BIT,A ;已到1S,依次开位选 SHOW_012345_J0: ;1S未到(FLAG_1S=0),继续显示 ACALL DISPLAY ...

    kgb档案压缩console版+源码

    where y_i is the i'th bit, and the context is the previous i - 1 bits of uncompressed data. 2. PAQ6 MODEL The PAQ6 model consists of a weighted mix of independent submodels which make predictions ...

    C语言讲义.doc

    printf("Argument count: %d\n", argc); for (int i = 0; i ; i++) { printf("Argument %d: %s\n", i, argv[i]); } return 0; } ``` ##### 1.3 注释 C语言支持两种注释方式:单行注释(`//`)和多行注释(`/* ...

    cpu的简单设计

    reg [20:0] count = 21'b0; Instruction_Mem instruction(clock,reset,i_addr,i_datain); PCPU pcpu(clock, enable, reset, start, d_datain, i_datain, select_y, i_addr, d_addr, d_dataout, d_we, y); ...

    S3C2410 LED驱动程序

    `MOD_INC_USE_COUNT`和`MOD_DEC_USE_COUNT`是用于增加和减少模块使用计数的宏,以防止模块被意外卸载。 ##### 8. 文件操作结构体 ```c staticstructfile_operationss3c2410_fops={ owner:THIS_MODULE, open:s3c...

    用C8051F单片机写的跑马灯C程序

    #define SYSCLK 24500000 //SYSCLK frequency in 24.5MHz #define T0_1ms 65536L-1*(SYSCLK/12000L) #define TH0S T0_1ms&gt;&gt;8 #define TL0S T0_1ms unsigned char dat; bit flag; unsigned int count;

    SV_FW_pro_random_costniy_systemverilog_in_

    constraint c { // 添加约束条件,例如限制元素范围或避免重复值 } ``` 接下来,成本函数(cost function)在随机化中用于指导生成更优解。它可以是任意表达式,其值越小,该解越“好”。当使用`do-while`循环进行...

    c8051f930中文版datasheet手册

    - 0.9–3.6 V operation with built-in dc-dc converter - Brownout detectors cover sleep and active modes - Low battery detector - Low BOM count - 5x6 36-pin QFN package Applications - Home automation - ...

    BIos原代码《陈文钦》

    ** (C)Copyright 1985-1996, American Megatrends Inc. **; ;** **; ;** All Rights Reserved. **; ;** **; ;** 6145-F, Northbelt Parkway, Norcross, **; ;** **; ;** Georgia - ...

    硬件设计—电子钟设计.pdf

    clk, clr: in bit; a, b, c, d: in std_logic_vector (3 downto 0); y, q: out std_logic_vector (3 downto 0) ); end mul4to1; architecture archmul4to1 of mul4to1 is variable count: integer; BEGIN ...

    计算机组成原理实验报告(含源码)

    int a, b, c, count, i; char t[16] = {0}; // 循环直到合法输入 rein: cout 请输入一个十进制数字(0~65535):" ; cin &gt;&gt; a; // 检查输入是否合法 if (a &gt; 65535 || a ) { cout 输入数字不合法,重新输入...

Global site tag (gtag.js) - Google Analytics