Monday Jun 04, 2007

How to write a program to output itsself's source code? (怎样写一个输出自己源代码的程序?)

来自:C FAQ 

要写一个可移植的自我再生的程序是件很困难的事, 部分原因是因为引用和字符集的难度。

这里是个经典的例子 (应该以一行表示的, 虽然第一次执行后它后自我修复):

    char\*s="char\*s=%c%s%c;main(){printf(s,34,s,34);}";
main(){printf(s,34,s,34);}

使用SunStudio11编译: cc -o setl_print self_print.c -g -Xs

Run:./ setl_print
char\*s="char\*s=%c%s%c;main(){printf(s,34,s,34);}";main(){printf(s,34,s,34);}

这段程序有一些依赖, 忽略了 #include <stdio.h>, 还假设了双引号 " 的值为 34, 和 ASCII 中的值一样。换行也没有了。

这里还有一个有 James Hu 发布的改进版:

    #define q(k)main(){return!puts(#k"\\nq("#k")");}
q(#define q(k)main(){return!puts(#k"\\nq("#k")");})

C language knowledge (3) -- Syntax and Operator precedence (C语言 基本知识3)

C language knowledge (3) -- Syntax and Operator precedence (C语言 基本知识3)

 

C (programming language)

From Wikipedia, the free encyclopedia

Syntax

Main article: C syntax

Operator precedence

Main article: Operators in C and C++

What follows is the list of C operators sorted from highest to lowest priority. Operators of same priority are presented on the same line. "R→L" associativity means that adjacent operators of the same priority are executed from right to left, and conversely for "L→R".

Class Associativity Operators
Select L→R (...) [...] -> .
Unary R→L ! ~ + - \* & (type) sizeof ++ --
Binary arithmetical L→R \* / %
Binary arithmetical L→R + -
Shift L→R << >>
Comparison L→R < <= > >=
Comparison L→R == !=
Binary bitwise L→R &
Binary bitwise L→R \^
Binary bitwise L→R |
Binary boolean L→R &&
Binary boolean L→R ||
Ternary R→L ?...:
Assignments R→L = += -= \*= /= &= |= \^= <<= >>=
Sequence L→R ,

另外有人总结出一个优先级的口诀可以帮助记忆:

醋坛酸味灌
味落跳福豆

共44个运算符

醋-初等,4个: ( ) [ ] -> 指向结构体成员 . 结构体成员
坛-单目,9个: ! ~ ++ -- -负号 (类型) \*指针 &取地址 sizeof长度
酸-算术,5个: \* / % + -减
味-位移,2个: << >>
灌-关系,6个: < <= > >= == 等于 != 不等于
味-位逻,3个: & 按位与 \^ 按位异或 | 按位或
落-逻辑,2个: && 逻辑与 || 逻辑或
跳-条件,1个: 三目: ? :
福-赋值,11个: = += -= \*= /= %= >>= <<= &= \^= |=
豆-逗号,1个: ,

结合方向自右向左的只有三类:赋值、单目和三目
同一优先级的运算顺序由结合方向决定

 

Sunday Jun 03, 2007

C language knowledge (2) -- History and Version (C语言 基本知识2)

C language knowledge (2) -- History and Version

 

C (programming language)

From Wikipedia, the free encyclopedia

History

Early developments

The initial development of C occurred at AT&T Bell Labs between 1969 and 1973; according to Ritchie, the most creative period occurred in 1972. It was named "C" because many of its features were derived from an earlier language called "B," which according to Ken Thompson was a stripped down version of the BCPL programming language.

There are many legends as to the origin of C and the closely related Unix operating system, including these:

  • The development of Unix was the result of programmers' desire to play the Space Travel computer game.[1] They had been playing it on their company's mainframe, but as it was underpowered and had to support about 100 users, Thompson and Ritchie found they did not have sufficient control over the spaceship to avoid collisions with the wandering space rocks. This led to the decision to port the game to an idle PDP-7 in the office. As this machine lacked an operating system, the two set out to develop one, based on several ideas from colleagues. Eventually it was decided to port the operating system to the office's PDP-11, but faced with the daunting task of translating a large body of custom-written assembly language code, the programmers began considering using a portable, high-level language so that the OS could be ported easily from one computer to another. They looked at using B, but it lacked functionality to take advantage of some of the PDP-11's advanced features. This led to the development of an early version of the C programming language.
  • The justification for obtaining the original computer to be used in developing the Unix operating system was to create a system to automate the filing of patents. The original version of the Unix system was developed in assembly language. Later, nearly all of the operating system was rewritten in C, an unprecedented move at a time when nearly all operating systems were written in assembly.

By 1973, the C language had become powerful enough that most of the Unix kernel, originally written in PDP-11 assembly language, was rewritten in C. This was one of the first operating system kernels implemented in a language other than assembly. (Earlier instances include the Multics system (written in PL/I), and MCP (Master Control Program) for the Burroughs B5000 written in ALGOL in 1961.)

Version

  •      K&R C
  •      ANSI CISO C
  •      C99

K&R C

In 1978, Dennis Ritchie and Brian Kernighan published the first edition of The C Programming Language. This book, known to C programmers as "K&R", served for many years as an informal specification of the language. The version of C that it describes is commonly referred to as "K&R C". The second edition of the book covers the later ANSI C standard.

K&R introduced several language features:

  • struct data types
  • long int data type
  • unsigned int data type
  • The =- operator was changed to -= to remove the semantic ambiguity created by the construct i=-10, which could be interpreted as either i =- 10 or i = -10

For many years after the introduction of ANSI C, K&R C was still considered the "lowest common denominator" to which C programmers restricted themselves when maximum portability was desired, since many older compilers were still in use, and because carefully written K&R C code can be legal ANSI C as well.

In early versions of C, only functions that returned a non-integer value needed to be declared if used before the function definition; a function used without any previous declaration was assumed to return an integer.

For example:

long int SomeFunction();
int OtherFunction();
 
int CallingFunction()
{
    long int test1;
    int test2;
 
    test1 = SomeFunction();
    if (test1 > 0) 
          test2 = 0;
    else 
          test2 = OtherFunction();
 
    return test2;
}

In the example, both SomeFunction and OtherFunction were declared before use. In K&R, OtherFunction declaration could be omitted.

Since K&R function declarations did not include any information about function arguments, function parameter type checks were not performed, although some compilers would issue a warning message if a local function was called with the wrong number of arguments, or if multiple calls to an external function used different numbers of arguments. Separate tools such as Unix's lint utility were developed that (among other things) could check for consistency of function use across multiple source files.

In the years following the publication of K&R C, several unofficial features were added to the language (since there was no standard), supported by compilers from AT&T and some other vendors. These included:

The large number of extensions and lack of a standard library, together with the language popularity and the fact that not even the Unix compilers precisely implemented the K&R specification, led to the necessity of standardization.

ANSI C and ISO C

During the late 1970s, C began to replace BASIC as the leading microcomputer programming language. During the 1980s, it was adopted for use with the IBM PC, and its popularity began to increase significantly. At the same time, Bjarne Stroustrup and others at Bell Labs began work on adding object-oriented programming language constructs to C, resulting in the language now called C++.

In 1983, the American National Standards Institute (ANSI) formed a committee, X3J11, to establish a standard specification of C. In 1989, the standard was ratified as ANSI X3.159-1989 "Programming Language C." This version of the language is often referred to as ANSI C, Standard C, or sometimes C89.

In 1990, the ANSI C standard (with a few minor modifications) was adopted by the International Organization for Standardization (ISO) as ISO/IEC 9899:1990. This version is sometimes called C90. Therefore, the terms "C89" and "C90" refer to essentially the same language.

One of the aims of the C standardization process was to produce a superset of K&R C, incorporating many of the unofficial features subsequently introduced. However, the standards committee also included several new features, such as function prototypes (borrowed from C++), void pointers, support for international character sets and locales, and a more capable preprocessor. The syntax for parameter declarations was also augmented to include the C++ style:

int main(int argc, char \*\*argv)
{
...
}

although the K&R interface

int main(argc, argv)
    int argc;
    char \*\*argv;
{
...
}

continued to be permitted, for compatibility with existing source code.

C89 is supported by current C compilers, and most C code being written nowadays is based on it. Any program written only in Standard C and without any hardware-dependent assumptions will run correctly on any platform with a conforming C implementation, within its resource limits. Without such precautions, programs may compile only on a certain platform or with a particular compiler, due, for example, to the use of non-standard libraries, such as GUI libraries, or to a reliance on compiler- or platform-specific attributes such as the exact size of data types and byte endianness.

In cases where code must be compilable by either standard-conforming or K&R C-based compilers, the __STDC__ macro can be used to split the code into Standard and K&R sections, in order to take advantage of features available only in Standard C.

#ifdef __STDC__
extern int getopt(int,char \* const \*,const char \*);
#else
extern int getopt();
#endif

In the above example, a compiler which has defined the __STDC__ macro (as mandated by the C standard) only interprets the line following the ifdef command. In other, nonstandard compilers which don't define the macro, only the line following the else command is interpreted.

C99

Note: C99 is also the name of a C compiler for the Texas Instruments TI-99/4A home computer. Aside from being a C compiler, it is otherwise unrelated.

After the ANSI standardization process, the C language specification remained relatively static for some time, whereas C++ continued to evolve, largely during its own standardization effort. Normative Amendment 1 created a new standard for the C language in 1995, but only to correct some details of the C89 standard and to add more extensive support for international character sets. However, the standard underwent further revision in the late 1990s, leading to the publication of ISO 9899:1999 in 1999. This standard is commonly referred to as "C99." It was adopted as an ANSI standard in March 2000.

New features

C99 introduced several new features, many of which had already been implemented as extensions in several compilers:

  • Inline functions
  • Variables can be declared anywhere (as in C++), rather than only after another declaration or the start of a compound statement
  • Several new data types, including long long int, optional extended integer types, an explicit boolean data type, and a complex type to represent complex numbers
  • Variable-length arrays
  • Support for one-line comments beginning with //, as in BCPL or C++
  • New library functions, such as snprintf
  • New header files, such as stdbool.h and inttypes.h
  • Type-generic math functions (tgmath.h)
  • Improved support for IEEE floating point
  • Designated initializers
  • Compound literals
  • Support for variadic macros (macros of variable arity)
  • restrict qualification to allow more aggressive code optimization

Details

C99 is for the most part upward-compatible with C90, but is stricter in some ways; in particular, a declaration that lacks a type specifier no longer has int implicitly assumed. The C standards committee decided that it was of more value for compilers to diagnose inadvertent omission of the type specifier than to silently process legacy code that relied on implicit int. In practice, compilers are likely to generate a warning.

Support by major compilers

GCC and other C compilers now support many of the new features of C99. However, there has been less support from vendors such as Microsoft and Borland that have mainly focused on C++, since C++ provides similar functionality improvement.

GCC, despite its extensive C99 support, is still not a completely compliant implementation; several key features are missing or don't work correctly.[2]

Version detection

A standard macro __STDC_VERSION__ is defined with value 199901L to indicate that C99 support is available. As with the __STDC__ macro for C90, __STDC_VERSION__ can be used to write code that will compile differently for C90 and C99 compilers, as in this example that ensures that inline is available in either case.

#if __STDC_VERSION__ >= 199901L
  /\* "inline" is a keyword \*/
#else
# define inline /\* nothing \*/
#endif

Reference:
http://en.wikipedia.org/wiki/C_(programming_language)

(中文)Chinese C wiki page: http://zh.wikipedia.org/wiki/C%E8%AF%AD%E8%A8%80
 

 

C language knowledge (1) -- Philosophy and Characteristics(C语言 基本知识1)

C language knowledge (1) -- Philosophy and Characteristics

 

C (programming language)

From Wikipedia, the free encyclopedia

C is a general-purpose, procedural, imperative computer programming language developed in 1972 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system.[1] It has since spread to many other platforms. Although predominantly used for system software,[2][3] C is also widely used for applications. C has also greatly influenced many other popular languages,[4] especially C++, which was designed as an enhancement to C.

Philosophy

C is an imperative (procedural) systems implementation language. Among its minimalistic design goals were that it could be compiled in a straightforward manner using a relatively simple compiler, provide low-level access to memory, generate only a few machine language instructions for each of its core language elements, and not require extensive run-time support. C is therefore suitable for many applications that had traditionally been implemented in assembly language.

Despite its low-level capabilities, the language was designed to encourage machine-independent programming. A standards-compliant and portably written C program can be compiled for a very wide variety of computer platforms and operating systems with minimal change to its source code. The language has become available on a very wide range of platforms, from embedded microcontrollers to supercomputers.

Characteristics

As most imperative languages in the ALGOL tradition, C has facilities for structured programming and allows lexical variable scope and recursion, while a static type system prevents many unintended operations. Parameters of C functions are always passed by value. Pass-by-reference is achieved in C by explicitly passing pointer values. Heterogeneous aggregate data types (the struct in C) allow related data elements to be combined and manipulated as a unit. C has around 30 reserved keywords and the source text is free-format, using semicolon as a statement terminator (not a delimiter).

C also exhibits the following more specific characteristics:

  • Non-nestable function definitions, although variables may be hidden in blocks to any level of depth
  • Partially weak typing, for instance, characters can be used as integers in a way similar to assembly
  • Low-level access to computer memory via machine addresses and typed pointers
  • Function pointers allowing for a rudimentary form of closures and runtime polymorphism
  • Array indexing as a secondary notion, defined in terms of pointer arithmetic
  • A standardized C preprocessor for macro definition, source code file inclusion, conditional compilation, etc.
  • Complex functionality such as I/O and mathematical functions consistently delegated to library routines
  • Syntax divergent from ALGOL, often following the lead of C's predecessor B, for example using
    • { ... } rather than ALGOL's begin ... end
    • the equal-sign for assignment (copying), much like Fortran
    • two consecutive equal-signs to test for equality (compare to .EQ. in Fortran or the equal-sign in BASIC)
    • && and || in place of ALGOL's and and or, which
      • are syntactically distinct from the bit-wise operators & and | (B used & and | in both meanings)
      • never evaluate the right operand if the result can be determined from the left alone (short-circuit evaluation)
    • a large number of compound operators, such as +=, ++, etc.

 

Reference:
http://en.wikipedia.org/wiki/C_(programming_language)

(中文)Chinese C wiki page: http://zh.wikipedia.org/wiki/C%E8%AF%AD%E8%A8%80
 

 

Wednesday May 30, 2007

Don't use these identifiers in C program. (不要在C程序里用的标识符)

If you want to write a portable C program, you have to be careful not to give your own definitions to any of the identifiers that are reserved by the C standard. The standard tells you which identifiers are reserved, but scatters the information through a rather thick (and expensive) book. 

The basic principles of reserved identifiers are in ISO subclause 7.1.3 (ANSI section 4.1.2.1), "Reserved Identifiers". There you are warned: 

if a program declares or defines an identifier with the same name as an identifier reserved in that context .., the behavior is undefined.

That means that if your program contains a statement like "extern int log;", the compiler is fully justified in turning your terminal into a large wart hog. Yes, the standard allows (3.16/1.6) such behavior, though market forces (and the laws of physics!) might not support it. More realistically, your program may or may not work right, and you may or may not get a diagnostic message. 

This page is descripte mostly identifiers which you should not use in C program.

Saturday May 26, 2007

How to reverse a string (如何反转字符串)

Question: How to Reverse a string in C? for example.input: “Hello world”, output:”dlrow olleH”

  • Most common way  :

 char\* strReverse1(char\* str)

{

    char \*temp=NULL, \*ptr=NULL;

    int len, i;

    temp=str;

       for(len=0; \*temp !='\\0';temp++, len++);

 
    ptr=(char\*)malloc(sizeof(char)\*(len+1));

 
    for(i=len-1; i>=0; i--)

        \*(ptr+len-i-1)=\*(str+i);

 
    \*(ptr+len)='\\0';

    return ptr;

}

Set the characters into a new buffer from last one to first.

Remark, In this method, new memory was malloced, so remember to free it after call this function.

 

  • Change the first one and last one, the second and (last -1)…

 char\* strReverse2(char\* str)

{

    int i=0, j=0, len=0;

    char temp='\\0';

    char \*ptr=NULL;

     
    len=strlen(str);

    ptr=(char\*)malloc(sizeof(char)\*(len+1));

    ptr=strcpy(ptr,str);

    for (i=0, j=len-1; i<=j; i++, j--) {

        temp=ptr[i];

        ptr[i]=ptr[j];

        ptr[j]=temp;

    }

    return ptr;

}

 
Remark, In this method, new memory was malloced, so remember to free it after call this function.

Here it a version with no new memory.

char\* strReverse3(char\* str)

{

    int i=0, j=0, len=0;

    char temp='\\0';

 
    len=strlen(str);

    for (i=0, j=len-1; i<=j; i++, j--) {

        temp=str[i];

        str[i]=str[j];

        str[j]=temp;

    }

    return str;

}

 
Operate poiter:

char\* strReverse4(char\* str)

{

    int i=0, j=0, len=0;

    char temp='\\0';

 
    len=strlen(str);

    for (i=0, j=len-1; i<=j; i++, j--) {

        temp=\*(str+i);

        \*(str+i)=\*(str+j);

        \*(str+j)=temp;

    }

    return str;

}

 

  • Memory optimize: exchange two char without tmp variable.

 
char\* strReverse5(char\* str)

{

    int i=0, j=0, len=0;

    len=strlen(str);

    for (i=0, j=len-1; i<j; i++, j--) {

        \*(str+i)\^= \*(str+j);

        \*(str+j)\^= \*(str+i);

        \*(str+i)\^= \*(str+j);

    }

    return str;

}

 
Key point: By XOR exchange a and b without using a third variable :

a=a\^b;
b=b\^a; //b\^a<=> b\^a\^b<=>a\^(b\^b)<=>a\^0=a
a=a\^b; // a\^b\^a<=>(a\^a)\^b<=>0\^b<=>b

Pretty C test code:       

a\^= b\^= a\^= b;

    printf("a = %d b = %d\\n", a, b);

这里利用了布尔代数地交换率和结合律,Chinese page:

http://wiki.ccw.com.cn/index.php?title=%E5%B8%83%E5%B0%94%E4%BB%A3%E6%95%B0&printable=yes&printable=yes

 

  • By recursion

void strReverse6(char\* str)

{

    if(\*str){

        strReverse6(str+1);

        \*strOut++ = \*str;

}

}

 
Test main program:

Char \*strOut=NULL;

main()

{

       char input[31]="";

       int len=0;

 

       sprintf(input, "Hello world");

       len = strlen(input);

       strOut = (char\*)malloc(sizeof(char)\*(len+1));

       memset(strOut, 0, len+1);

 

    strReverse6(input);

       printf("strReverse6:%s\\n", strOut);

       free(strOut);

}

Use a global variable strOut to store the reversed result string.

 

Reference:

http://everything2.com/index.pl?node_id=612464

http://discuss.fogcreek.com/techinterview/default.asp?cmd=show&ixPost=2077

Tuesday May 22, 2007

Count the number of bits that are on in an unsigned integer(计算一个无符整数中1Bit的个数) -- (2)

(接上篇)

原创整理,转载请注明出处。

7合并计数器法的优化

优化1

算法的优化:基于以下两点合并计数器法可以进行优化:

1)        和的存储空间为 log2 (the number of bits being counted)\*coutern number.随着(coutern number)减少,需要的存储bit减少。但是实际每次都被存储在一个32位整数。

2)        在多数架构中,简单的8-bit的常量比32-bit的更容易构造。

基于以上2点,最后的一步:

i = (i&MASK16) + (i>>16&MASK16)

可以变成:

i = (i + (i>>16))&MASK6;

MASK6(1<<6)-1 or 0x1F,可以消除需要进行MASK16的操作。

经过这样的优化,可以节省两个操作:建立各大整数常量 一个与(AND)操作

unsigned numbits(unsigned int v)
{
    unsigned int const MASK1  = 0x55555555;
    unsigned int const MASK2  = 0x33333333;
    unsigned int const MASK4  = 0x0f0f0f0f;
    unsigned int const MASK6 = 0x0000003f;
 
    unsigned int const w = (v & MASK1) + ((v >> 1) & MASK1);
    unsigned int const x = (w & MASK2) + ((w >> 2) & MASK2);
    unsigned int const y = (x + (x >> 4) & MASK4);
    unsigned int const z = (y + (y >> 8));
    unsigned int const c = (z + (z >> 16)) & MASK6;
 
    return c;
}

举个例子,假设输入的i值为10010111011111010101101110101111(十进制2541575087

计算过程如下:(共221

1.        32个计数器合并为16,每一个计数器代表 2-bit 1个数

 1 0 0 1 0 1 1 0 0 0 1 1 1 1 1 1 =  1  0  0  1  0  1  1  0  0  0  1  1  1  1  1  1

+0 1 1 1 1 1 1 1 1 1 0 1 0 0 1 1 =  0  1  1  1  1  1  1  1  1  1  0  1  0  0  1  1

 ----------------------------------------------------------------------

 1 1 1 2 1 2 2 1 1 1 1 2 1 1 2 2 = 01 01 01 10 01 10 10 01 01 01 01 10 01 01 10 10

2.        16个计数器合并为8,每一个计数器代表 4-bit 1个数

 1 1 1 2 1 1 1 2 =   01   01   01   10   01   01   01   10

+1 2 2 1 1 2 1 2 =   01   10   10   01   01   10   01   10

 ---------------   ---------------------------------------

 2 3 3 3 2 3 2 4 = 0010 0011 0011 0011 0010 0011 0010 0100

3.        8个计数器合并为4,每一个计数器代表 8-bit 1个数:y = (x + (x >> 4) & MASK4)

                    0010 0011 0011 0011 0010 0011 0010 0100

+                   0000 0010 0011 0011 0011 0010 0011 0010

 -------   ---------------------------------------------------

0010 0101 0110 0110 0101 0101 0101 0110

&MASK4       0000 1111 0000 1111 0000 1111 0000 1111

-------   --------------------------------------------------

0000 0101 0000 0110 0000 0101 0000 0110

4.        计算相邻的每对(只有2,4Counter8bit计数器的和(不进行合并计数器的操作)。

        0000 0101 0000 0110 0000 0101 0000 0110

+     0000 0000 0000 0101 0000 0110 0000 0101  

 -----   ---------------------------------

0000 0101 0000 1011 0000 1011 0000 1011

5.        计算最后一对Counter(16BitCounter)的和,并根据掩码求出世纪的有效数字。其实将45步的与掩码运算合并为只进行一次。

     0000 0101 0000 1011 0000 1011 0000 1011

     0000 0000 0000 0000 0000 0101 0000 1011

     --   --------------------------------

  0000 0101 0000 1011 0001 0000 0001 0110

&MASK6   0000 0000 0000 0000 0000 0000 0011 1111

      --   --------------------------------

           0000 0000 0000 0000 0000 0000 0001 0110 = 22

 

优化2

然而以上的算法,仍然可以优化为:这也许是最好的算法了。

unsigned numbits(unsigned int v)
{
    unsigned int const MASK1 = 0x55555555;
    unsigned int const MASK2 = 0x33333333;
    unsigned int const MASK4 = 0x0f0f0f0f;
 
    unsigned int const w = v - ((v >> 1) & MASK1);
    unsigned int const x = (w & MASK2) + ((w >> 2) & MASK2);
    unsigned int const y = (x + (x >> 4) & MASK4);
    unsigned int const c = (y \* 0x01010101) >> 24;
 
    return c;
}

与优化1比较,又进行了以下两点优化:

      1)        为了在第一行不使用AND操作,替换相邻位相加的操作为:v减去它的右移操作后与掩码操作的结果。这个结果以相同的。00 - 0 = 0, 01 - 0 = 01, 10 - 1 = 01, 11 - 1 = 10

即:

       v= (v&MASK1 ) + (v>>1 &MASK1 );

w = v - ((v >> 1) & MASK1);

v=w

2)        为了合并最后两行,使用了一个乘法运算(00000001 00000001 00000001 00000001)和一个位移操作(只取最右边6位),这样的处理在一步就累加了4Bit大小的计数器。可以回忆乘法运算的竖式计算法,就是对第三步的结果Y,分为每8bit大小的四组,然后求和。

 

优化3

还可以进行如下的优化:

#define MASK_01010101 (((unsigned int)(-1))/3)
#define MASK_00110011 (((unsigned int)(-1))/5)
 #define MASK_00001111 (((unsigned int)(-1))/17)
 
 int bitcount (unsigned int n)
 {
    n = (n & MASK_01010101) + ((n >> 1) & MASK_01010101) ; 
    n = (n & MASK_00110011) + ((n >> 2) & MASK_00110011) ; 
    n = (n & MASK_00001111) + ((n >> 4) & MASK_00001111) ; 
    return n % 255 ;
 }

请根据除法的意义思考为什么取255的余数。

 

8 MIT_HACKEMEM计数法MIT HACKMEM Count

int bitcount(unsigned int n)                          
{
    /\* works for 32-bit numbers only    \*/
    /\* fix last line for 64-bit numbers \*/
register unsigned int tmp;
 
    tmp = n - ((n >> 1) & 033333333333)
            - ((n >> 2) & 011111111111);
   return ((tmp + (tmp >> 3)) & 030707070707) % 63;
}

这是一种很巧妙的算法:

考虑一个3Bit数N,可以看成4a+2b+c(a,b,c为0 或者1), 如果右移一位,得到2a+b,然后从原始的数(4a+2b+c)里减去2a+b,(N-N>>1)差为2a+b+c。如果右移两位,得到a,然后用刚才得到的差2a+b+c减去a,(即(N-N>>1-N>>2)结果是a+b+c,这就是原始的数字里Bit为1的个数。

这个算法如何实现呢?首先声明一个临时变量tmp。认为tmp8进制描述的。8进制的每个数字都是n中相应的每3Bit位所描述的数字。最后返回这些8进制数的和就是我们需要的最终答案了。关键是,将相邻的8进制对加在一起,然后计算时记得对63(2(3+3)次幂)-1)进行除运算取得余数。实现方法是:使用tmp右移3位、然后与自身相加,再与一个适当的掩码进行AND操作,产生一个数,这个数是相邻6位中含有Bit1的个数。

64位数来说,应该比8进制数的多3倍(4倍),所以要对102364\*24次幂)-1)求模。(这算法在X11代码中被用到过。)

 

参考:

http://www.everything2.com/index.pl?node_id=1181258

http://infolab.stanford.edu/~manku/bitcount/bitcount.html

Sunday May 20, 2007

Count the number of bits that are on in an unsigned integer(计算一个无符整数中1Bit的个数)-- (1)

计算一个无符号整数中有多少的Bit为1

原创整理,转载请注明出处。

这是一个经常遇到的经典问题,这里分两个部分讲解和总结,首先对讲解现有的算法,然后再讲解一些改进算法。

 

1.循环法(Iterated Count

int bitcount (unsigned int n)  
{
int count=0;    
    while (n)  {
      count += n & 0x1u ;
      n >>= 1 ;
    }
return count ;
}

最容易理解和想到的方法。对每一位依次判断是否为1,如果是就在count上加1

循环的次数是常数(n的位数)。在1比较稀疏的时候效率低,可用方法2改进。

 

2Bit1稀疏Sparse Ones

int bitcount (unsigned int n)  
{
int count=0 ;
       while (n)  {
       count++ ;
       n &= (n - 1) ;
   }
   return count ;
}

理解这个算法的核心,只需理解2个操作:

  1> 当一个数被减1时,他最右边的那个值为1Bit将变为0,同时其右边的所有的Bit都会变成1
  2>“&=”,位与并赋值操作。去掉已经被计数过的1,并将改值重新设置给n.

这个算法循环的次数是bit位为一的个数。也就说有几个Bit1,循环几次。对Bit1比较稀疏的数来说,性能很好。如:0x1000 0000, 循环一次就可以。

 

3.密集1的算法 Dense Ones

   int bitcount (unsigned int n)    

   {

      int count = 8 \* sizeof(int) ;

      n \^= (unsigned int) -1 ;

      while (n)

      {

         count-- ;

         n &= (n - 1) ;

      }

      return count ;

   }

2稀疏1的算法相类似。不同点是,针对1密集的情况,循环的次数会大大减少。他的循环次数:sizeof(int)-Bit 1的个数。

 

48bit静态表查找法 Precompute_8bit

   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

};


  

  
   int 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] ;
   }

使用静态数组表,列出所有8bit(256)无符号数含有Bit1的个数。将32Bit n4部分,直接在表中找到对应的Bit1的个数,然后求和。

这是最快的方法了。缺点是需要比较大的内存。

  

516bit静态表查找法Precompute_16bit

因为在计算64int时,以上方法4并不总是最快,所以有以下的一个进化版,就是用十六Bit的表来作驱动映射。这样需要的内存就更大了。

 static char bits_in_16bits [0x1u << 16] …;

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

 

6. 合并计数器法 Parallel Counter

 unsigned numbits(unsigned int i)

{

  
    unsigned int const MASK1  = 0x55555555;
    unsigned int const MASK2  = 0x33333333;
    unsigned int const MASK4  = 0x0f0f0f0f;
    unsigned int const MASK8  = 0x00ff00ff;
unsigned int const MASK16 = 0x0000ffff;
/\*
MASK1  = 01010101010101010101010101010101
MASK2  = 00110011001100110011001100110011
MASK4  = 00001111000011110000111100001111
MASK8  = 00000000111111110000000011111111
MASK16 = 00000000000000001111111111111111
\*/

  
    
    i = (i&MASK1 ) + (i>>1 &MASK1 );
    i = (i&MASK2 ) + (i>>2 &MASK2 );
    i = (i&MASK4 ) + (i>>4 &MASK4 );
    i = (i&MASK8 ) + (i>>8 &MASK8 );
    i = (i&MASK16) + (i>>16&MASK16);
    
    return i;
}

这个算法是一种合并计数器的策略。把输入数的32Bit当作32个计数器,代表每一位的1个数。然后合并相邻的2个“计数器”,使i成为16个计数器,每个计数器的值就是这2Bit1的个数;继续合并相邻的2个“计数器“,使i成为8个计数器,每个计数器的值就是4Bit1的个数。。依次类推,直到将i变成一个计数器,那么它的值就是32Biti中值为1Bit的个数。

举个例子,假设输入的i值为10010111011111010101101110101111(十进制2541575087

计算过程如下:(共221

1.        32个计数器合并为16,每一个计数器代表 2-bit 1个数

 1 0 0 1 0 1 1 0 0 0 1 1 1 1 1 1 =  1  0  0  1  0  1  1  0  0  0  1  1  1  1  1  1

+0 1 1 1 1 1 1 1 1 1 0 1 0 0 1 1 =  0  1  1  1  1  1  1  1  1  1  0  1  0  0  1  1

 ----------------------------------------------------------------------

 1 1 1 2 1 2 2 1 1 1 1 2 1 1 2 2 = 01 01 01 10 01 10 10 01 01 01 01 10 01 01 10 10

2.        16个计数器合并为8,每一个计数器代表 4-bit 1个数

 1 1 1 2 1 1 1 2 =   01   01   01   10   01   01   01   10

+1 2 2 1 1 2 1 2 =   01   10   10   01   01   10   01   10

 ---------------   ---------------------------------------

 2 3 3 3 2 3 2 4 = 0010 0011 0011 0011 0010 0011 0010 0100

3.        8个计数器合并为4,每一个计数器代表 8-bit 1个数

 3 3 3 4 =     0010     0011     0010     0010

+2 3 2 2 =     0011     0011     0011     0100

 -------   -----------------------------------

 5 6 5 6 = 00000101 00000110 00000101 00000110

4.        4个计数器合并为2,每一个计数器代表 16-bit 1个数

  5  5 =         00000101         00000101

+ 6  6 =         00000110         00000110

 -----   ---------------------------------

 11 11 = 0000000000001011 0000000000001011

5.        最后,将2个计数器合并为1,每一个计数器代表 32-bit (也就是输入的值i)的1个数

 11 =                 0000000000001011

+11 =                 0000000000001011

 --   --------------------------------

 22 = 00000000000000000000000000010110

 

对于该算法的实现,另外有一种比较好的写法,这种算法避免了使用常数宏,使比较通用的实现:

  #define TWO(c)     (0x1u << (c))
  #define MASK(c)    (((unsigned int)(-1)) / (TWO(TWO(c)) + 1u))
  #define COUNT(x,c) ((x) & MASK(c)) + (((x) >> (TWO(c))) & MASK(c))
  int bitcount (unsigned int n)
  {
     n = COUNT(n, 0) ;
     n = COUNT(n, 1) ;
     n = COUNT(n, 2) ;
     n = COUNT(n, 3) ;
     n = COUNT(n, 4) ;
     /\* n = COUNT(n, 5) ;    for 64-bit integers \*/
     return n ;
  }

下面将讲解一些改进的算法。 

待续。。。

 

参考:

http://www.everything2.com/index.pl?node_id=1181258

http://infolab.stanford.edu/~manku/bitcount/bitcount.html

About

williamxue

Search

Categories
Archives
« April 2014
SunMonTueWedThuFriSat
  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
   
       
Today