Learning C with gdb

原文地址： https://www.hackerschool.com/blog/5-learing-c-with-gdb

Coming from a background in higher-level languages like Ruby, Scheme, or Haskell, learning C can be challenging. In addition to having to wrestle with C's lower-level features like manual memory management and pointers, you have to make do without a REPL. Once you get used to exploratory programming in a REPL, having to deal with the write-compile-run loop is a bit of a bummer.

It occurred to me recently that I could use gdb as a pseudo-REPL for C. I've been experimenting with using gdb as a tool for learning C, rather than merely debugging C, and it's a lot of fun.

My goal in this post is to show you that gdb is a great tool for learning C. I'll introduce you to a few of my favorite gdb commands, and then I'll demonstrate how you can use gdb to understand a notoriously tricky part of C: the difference between arrays and pointers.

An introduction to gdb

Start by creating the following little C program, minimal.c:

int main()
{
    int i = 1337;
    return 0;
}

Note that the program does nothing and has not a single printf statement.¹ Behold the brave new world of learning C with gdb!

Compile it with the -g flag so that gdb has debug information to work with, and then feed it to gdb:

$ gcc -g minimal.c -o minimal
$ gdb minimal

You should now find yourself at a rather stark gdb prompt. I promised you a REPL, so here goes:

(gdb) print 1 + 2
$1 = 3

Amazing! print is a built-in gdb command that prints the evaluation of a C expression. If you're unsure of what a gdb command does, try running help name-of-the-command at the gdb prompt.

Here's a somewhat more interesting example:

(gbd) print (int) 2147483648
$2 = -2147483648

I'm going to ignore why 2147483648 == -2147483648; the point is that even arithmetic can be tricky in C, and gdb understands C arithmetic.

Let's now set a breakpoint in the main function and start the program:

(gdb) break main
(gdb) run

The program is now paused on line 3, just before i gets initialized. Interestingly, even though i hasn't been initialized yet, we can still look at its value using the print commnd:

(gdb) print i
$3 = 32767

In C, the value of an uninitialized local variable is undefined, so gdb might print something different for you!

We can execute the current line with the next command:

(gdb) next
(gdb) print i
$4 = 1337

Examining memory with x

Variables in C label contiguous chunks of memory. A variable's chunk is characterized by two numbers:

1. The numerical address of the first byte in the chunk.
2. The size of the chunk, measured in bytes. The size of a variable's chunk is determined by the variable's type.

One of the distinctive features of C is that you have direct access to a variable's chunk of memory. The & operator computes a variable's address, and the sizeof operator computes a variable's size in memory.

You can play around with both concepts in gdb:

(gdb) print &i
$5 = (int *) 0x7fff5fbff584
(gdb) print sizeof(i)
$6 = 4

In words, this says that i's chunk of memory starts at address 0x7fff5fbff5b4 and takes up four bytes of memory.

I mentioned above that a variable's size in memory is determined by its type, and indeed, thesizeof operator can operate directly on types:

(gdb) print sizeof(int)
$7 = 4
(gdb) print sizeof(double)
$8 = 8

This means that, on my machine at least, int variables take up four bytes of space anddouble variables take up eight.

Gdb comes with a powerful tool for directly examing memory: the x command. The xcommand examines memory, starting at a particular address. It comes with a number of formatting commands that provide precise control over how many bytes you'd like to examine and how you'd like to print them; when in doubt, try running help x at the gdb prompt.

The & operator computes a variable's address, so that means we can feed &i to x and thereby take a look at the raw bytes underlying i's value:

(gdb) x/4xb &i
0x7fff5fbff584: 0x39    0x05    0x00    0x00

The flags indicate that I want to examine 4 values, formatted as hex numerals, one byte at a time. I've chosen to examine four bytes because i's size in memory is four bytes; the printout shows i's raw byte-by-byte representation in memory.

One subtlety to bear in mind with raw byte-by-byte examinations is that on Intel machines, bytes are stored in "little-endian" order: unlike human notation, the least significant bytes of a number come first in memory.

One way to clarify the issue would be to give i a more interesting value and then re-examine its chunk of memory:

(gdb) set var i = 0x12345678
(gdb) x/4xb &i
0x7fff5fbff584: 0x78    0x56    0x34    0x12

Examining types with ptype

The ptype command might be my favorite command. It tells you the type of a C expression:

(gdb) ptype i
type = int
(gdb) ptype &i
type = int *
(gdb) ptype main
type = int (void)

Types in C can get complex but ptype allows you to explore them interactively.

Pointers and arrays

Arrays are a surprisingly subtle concept in C. The plan for this section is to write a simple program and then poke it in gdb until arrays start to make sense.

Code up the following arrays.c program:

int main()
{
    int a[] = {1,2,3};
    return 0;
}

Compile it with the -g flag, run it in gdb, then next over the initialization line:

$ gcc -g arrays.c -o arrays
$ gdb arrays
(gdb) break main
(gdb) run
(gdb) next

At this point you should be able to print the contents of a and examine its type:

(gdb) print a
$1 = {1, 2, 3}
(gdb) ptype a
type = int [3]

Now that our program is set up correctly in gdb, the first thing we should do is use x to see what a looks like under the hood:

(gdb) x/12xb &a
0x7fff5fbff56c: 0x01  0x00  0x00  0x00  0x02  0x00  0x00  0x00
0x7fff5fbff574: 0x03  0x00  0x00  0x00

This means that a's chunk of memory starts at address 0x7fff5fbff5dc. The first four bytes store a[0], the next four store a[1], and the final four store a[2]. Indeed, you can check that sizeof knows that a's size in memory is twelve bytes:

(gdb) print sizeof(a)
$2 = 12

At this point, arrays seem to be quite array-like. They have their own array-like types and store their members in a contiguous chunk of memory. However, in certain situations, arrays act a lot like pointers! For instance, we can do pointer arithmetic on a:

(gdb) print a + 1
$3 = (int *) 0x7fff5fbff570

In words, this says that a + 1 is a pointer to an int and holds the address0x7fff5fbff570. At this point you should be reflexively passing pointers to the xcommand, so let's see what happens:

(gdb) x/4xb a + 1
0x7fff5fbff570: 0x02  0x00  0x00  0x00

Note that 0x7fff5fbff570 is four more than 0x7fff5fbff56c, the address of a's first byte in memory. Given that int values take up four bytes, this means that a + 1 points to a[1].

In fact, array indexing in C is syntactic sugar for pointer arithmetic: a[i] is equivalent to *(a + i). You can try this in gdb:

(gdb) print a[0]
$4 = 1
(gdb) print *(a + 0)
$5 = 1
(gdb) print a[1]
$6 = 2
(gdb) print *(a + 1)
$7 = 2
(gdb) print a[2]
$8 = 3
(gdb) print *(a + 2)
$9 = 3

We've seen that in some situations a acts like an array and in others it acts like a pointer to its first element. What's going on?

The answer is that when an array name is used in a C expression, it "decays" to a pointer to the array's first element. There are only two exceptions to this rule: when the array name is passed to sizeof and when the array name is passed to the & operator.²

The fact that a doesn't decay to a pointer when passed to the & operator brings up an interesting question: is there a difference between the pointer that a decays to and &a?

Numerically, they both represent the same address:

(gdb) x/4xb a
0x7fff5fbff56c: 0x01  0x00  0x00  0x00
(gdb) x/4xb &a
0x7fff5fbff56c: 0x01  0x00  0x00  0x00

However, their types are different. We've already seen that the decayed value of a is a pointer to a's first element; this must have type int *. As for the type of &a, we can ask gdb directly:

(gdb) ptype &a
type = int (*)[3]

In words, &a is a pointer to an array of three integers. This makes sense: a doesn't decay when passed to &, and a has type int [3].

You can observe the distinction between a's decayed value and &a by checking how they behave with respect to pointer arithmetic:

(gdb) print a + 1
$10 = (int *) 0x7fff5fbff570
(gdb) print &a + 1
$11 = (int (*)[3]) 0x7fff5fbff578

Note that adding 1 to a adds four to a's address, whereas adding 1 to &a adds twelve!

The pointer that a actually decays to is &a[0]:

(gdb) print &a[0]
$11 = (int *) 0x7fff5fbff56c

Conclusion

Hopefully I've convinced you that gdb a neat exploratory environment for learning C. You can print the evaluation of expressions, examine raw bytes in memory, and tinker with the type system using ptype.

If you'd like to experiment further with using gdb to learn C, I have a few suggestions:

1. Use gdb to work through the Ksplice pointer challenge.
2. Investigate how structs are stored in memory. How do they compare to arrays?
3. Use gdb's disassemble command to learn assembly programming! A particularly fun exercise is to investigate how the function call stack works.
4. Check out gdb's "tui" mode, which provides a grahical ncurses layer on top of regular gdb. On OS X, you'll likely need to install gdb from source.

Knuth-shuffle洗牌算法

要写出一个真正随机(我意思是均匀分布)的洗牌程序并不容易，即使强如Jeff Atwood也是 会写错的。Jeff写错的版本是这样的：

//error!
for(int i=0;i<cards.Length;i++){
    int n = rand.Next(cards.Length);
    Swap(ref cards[i],ref cards[n]);
}

问题在于我们并不能轻易地看出这段程序生成的排列不是均匀分布的（容我想想，我现在看 得出么…）。

实际上，是有个O(n)的洗牌算法 Fisher-Yates,又称为Knuth-shuffle(Knuth在TAOCP介绍过 而得名)：

//To shuffle an array a of n elements (indices 0..n-1):
for i from n − 1 downto 1 do
       j <- random integer with 0 ≤ j ≤ i
       exchange a[j] and a[i]

这个算法就地洗牌，但它需要预先知道洗牌数组的长度。它的正确性(也就是生成的排列是 否均匀分布)不难看出。

Knuth-shuffle还有另一种实现：

//To initialize an array a of n elements to a randomly shuffled copy of
//source, both 0-based: 
a[0] <- source[0]
for i from 1 to n − 1 do
    j <- random integer with 0 ≤ j ≤ i
    a[i] <- a[j]
    a[j] <- source[i]

这个实现的正确性可以这么考虑：对于n-1次random调用生成的n!次随机序列，总会对应不 同的排列，所以n!次排列是均匀分布的。

这个实现有一个坏处，它需要额外的数组来存储生成的排列。但它也有一个大大的好处，它 可以不用预先知道数组的长度:

//To initialize an empty array a to a randomly shuffled copy of source whose
//length is not know:
while source.moreDataAvailable
    j <- random integer with 0 ≤ j ≤ a.length
    if j = a.length
        a.append(source.next)
    else
        a.append(a[j])
        a[j] <- source.next

Knuth-shuffle做些修改还可以有别的应用。比如下面这个问题：

1. 如何从未知长度的序列中均匀地随机选择一个数？要求最多只遍历一遍。
2. 如何从未知长度的序列中均匀地随机选择k个数？要求最多只遍历一遍。

.

问题(1)参考程序:

import random

def random_element(seq):
    """Return an element chosen at random from `seq`."""
    it = None
    for n, elem in enumerate(seq):
        if random.randint(0, n) == 0:
            it = elem
    return it

问题(2)参考程序:

import random

def random_sample(n, items):
    results = []

    for i, v in enumerate(items):
        r = random.randint(0, i)
        if r < n:
            if i < n:
                results.insert(r, v) # add first n items in random order
            else:
                #at a decreasing rate,replace random items
                results[r] = v 

    if len(results) < n:
        raise ValueError("Sample larger than population.")

    return results

参考资料

1. http://www.codinghorror.com/blog/2007/12/the-danger-of-naivete.html
2. http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
3. http://nedbatchelder.com/blog/201208/selecting_randomly_from_an_unknown_sequence.html
4. http://stackoverflow.com/questions/12128948/python-random-lines-from-subfolders/12134726#12134726

enum的小问题

在这个博客上看到这样一个问题:

//问题1
//foo函数输出什么?
enum MY_ENUM{
  MY_OK = 0,
  MY_NOT_OK,
}

void foo()
{
   int i = -1;
   enum My_ENUM my_enum = MY_OK;

   if( i < my_enum) printf("I am OK!\n");
   else printf("I am NOT OK!\n");

}

如果对上面的函数做小小的修改，又是什么结果？

//问题2
//foo函数输出什么？
enum MY_ENUM{
  MY_OK = 0,
  MY_NOT_OK,
}

void foo()
{
   int i = -1;
   enum My_ENUM my_enum = MY_OK;

   if( i < MY_OK) printf("I am OK!\n");
   else printf("I am NOT OK!\n");

}

FOR THE MARGIN. HAVE BETTER MATHOD?

文中给出的答案是问题1输出"I am NOT OK!",而问题2输出"I am OK!".多多少少让我有点琢 磨不透，为什么会这样呢？

实际上，正如文中提到的，gcc确实是这样的结果。但如果同样的程序在msvc去运行，就会发 现问题1和问题2都是输出"I am OK!". 这是跟编译器实现有关的问题。在gcc中，当enum常数 (所谓的enum常数就是enum类型中标记的那些值，如程序中的MY_OK)没有负数时，gcc将 enum类型变量（注意与enum常数的区别，如程序中的my_enum）存储为无符号int。当enum常 数有负数时，则仍然乖乖地存储为int。而enum常数是一直都存储为int。msvc则是不管什么 情况，都将enum常数和enum类型存储为int。在这个实现上，我觉得gcc真是吃饱了撑的，你 觉得呢？

综上所述，这是个不好的问题。姑且一笑而过。

参考资料

1. http://gcc.gnu.org/onlinedocs/gcc/Structures-unions-enumerations-and-bit_002dfields-implementation.html
2. http://msdn.microsoft.com/en-us/library/whbyts4t.aspx

java对象模型

原文地址：http://www.codeinstructions.com/2008/12/java-objects-memory-structure.html

Update (December 18th, 2008): I've posted here an experimental library that implements Sizeof for Java.

One thing about Java that has always bothered me, given my C/C++ roots, is the lack of a way to figure out how much memory is used by an object. C++ features the sizeof operator, that lets you query the size of primitive types and also the size of objects of a given class. This operator in C and C++ is useful for pointer arithmetic, copying memory around, and IO, for example.

Java doesn't have a corresponding operator. In reality, Java doesn't need one. Size of primitive types in Java is defined in the language specification, whereas in C and C++ it depends on the platform. Java has its own IO infrastructure built around serialization. And both pointer arithmetic and bulk memory copy don't apply because Java doesn't have pointers.

But every Java developer at some point wondered how much memory is used by a Java object. The answer, it turns out, is not so simple.

The first distinction to be made is between shallow size and deep size. The shallow size of an object is the space occupied by the object alone, not taking into account size of other objects that it references. The deep size, on the other hand, takes into account the shallow size of the object, plus the deep size of each object referenced by this object, recursively. Most of the times you will be interested on knowing the deep size of an object, but, in order to know that, you need to know how to calculate the shallow size first, which is what I'm going to talk about here.

One complication is that runtime in memory structure of Java objects is not enforced by the virtual machine specification, which means that virtual machine providers can implement them as they please. The consequence is that you can write a class, and instances of that class in one VM can occupy a different amount of memory than instances of that same class when run in another VM. Most of the world, including myself, uses the Sun HotSpot virtual machine though, which simplifies things a lot. The remainder of the discussion will focus on the 32 bit Sun JVM. I will lay down a few 'rules that will help explain how the JVM organizes the objects' layout in memory.

Memory layout of classes that have no instance attributes

In the Sun JVM, every object (except arrays) has a 2 words header. The first word contains the object's identity hash code plus some flags like lock state and age, and the second word contains a reference to the object's class. Also, any object is aligned to an 8 bytes granularity. This is the first rule or objects memory layout:

Rule 1: every object is aligned to an 8 bytes granularity.

Now we know that if we call new Object(), we will be using 8 bytes of the heap for the two header words and nothing else, since the Objectclass doesn't have any fields.

Memory layout of classes that extend Object

After the 8 bytes of header, the class attributes follow. Attributes are always aligned in memory to their size. For instance, ints are aligned to a 4 byte granularity, and longs are aligned to an 8 byte granularity. There is a performance reason to do it this way: usually the cost to read a 4 bytes word from memory into a 4 bytes register of the processor is much cheaper if the word is aligned to a 4 bytes granularity.

In order to save some memory, the Sun VM doesn't lay out object's attributes in the same order they are declared. Instead, the attributes are organized in memory in the following order:

1. doubles and longs
2. ints and floats
3. shorts and chars
4. booleans and bytes
5. references

This scheme allows for a good optimization of memory usage. For example, imagine you declared the following class:

class MyClass {
    byte a;
    int c;
    boolean d;
    long e;
    Object f;        
}

If the JVM didn't reorder the attributes, the object memory layout would be like this:

[HEADER:  8 bytes]  8
[a:       1 byte ]  9
[padding: 3 bytes] 12
[c:       4 bytes] 16
[d:       1 byte ] 17
[padding: 7 bytes] 24
[e:       8 bytes] 32
[f:       4 bytes] 36
[padding: 4 bytes] 40

Notice that 14 bytes would have been wasted with padding and the object would use 40 bytes of memory. By reordering the objects using the rules above, the in memory structure of the object becomes:

[HEADER:  8 bytes]  8
[e:       8 bytes] 16
[c:       4 bytes] 20
[a:       1 byte ] 21
[d:       1 byte ] 22
[padding: 2 bytes] 24
[f:       4 bytes] 28
[padding: 4 bytes] 32

This time, only 6 bytes are used for padding and the object uses only 32 bytes of memory.

So here is rule 2 of object memory layout:

Rule 2: class attributes are ordered like this: first longs and doubles; then ints and floats; then chars and shorts; then bytes and booleans, and last the references. The attributes are aligned to their own granularity.

Now we know how to calculate the memory used by any instance of a class that extends Object directly. One practical example is the java.lang.Boolean class. Here is its memory layout:

[HEADER:  8 bytes]  8 
[value:   1 byte ]  9
[padding: 7 bytes] 16

An instance of the Boolean class takes 16 bytes of memory! Surprised? (Notice the padding at the end to align the object size to an 8 bytes granularity.)

Memory layout of subclasses of other classes

The next three rules are followed by the JVM to organize the the fields of classes that have superclasses. Rule 3 of object memory layout is the following:

Rule 3: Fields that belong to different classes of the hierarchy are NEVER mixed up together. Fields of the superclass come first, obeying rule 2, followed by the fields of the subclass.

Here is an example:

class A {
   long a;
   int b;
   int c;
}

class B extends A {
   long d;
}

An instance of B looks like this in memory:

[HEADER:  8 bytes]  8
[a:       8 bytes] 16
[b:       4 bytes] 20
[c:       4 bytes] 24
[d:       8 bytes] 32

The next rule is used when the fields of the superclass don't fit in a 4 bytes granularity. Here is what it says:

Rule 4: Between the last field of the superclass and the first field of the subclass there must be padding to align to a 4 bytes boundary.

Here is an example:

class A {
   byte a;
}

class B {
   byte b;
}

[HEADER:  8 bytes]  8
[a:       1 byte ]  9
[padding: 3 bytes] 12
[b:       1 byte ] 13
[padding: 3 bytes] 16

Notice the 3 bytes padding after field a to align b to a 4 bytes granularity. That space is lost and cannot be used by fields of class B.

The final rule is applied to save some space when the first field of the subclass is a long or double and the parent class doesn't end in an 8 bytes boundary.

Rule 5: When the first field of a subclass is a double or long and the superclass doesn't align to an 8 bytes boundary, JVM will break rule 2 and try to put an int, then shorts, then bytes, and then references at the beginning of the space reserved to the subclass until it fills the gap.

Here is an example:

class A {
  byte a;
}

class B {
  long b;
  short c;  
  byte d;
}

Here is the memory layout:

[HEADER:  8 bytes]  8
[a:       1 byte ]  9
[padding: 3 bytes] 12
[c:       2 bytes] 14
[d:       1 byte ] 15
[padding: 1 byte ] 16
[b:       8 bytes] 24

At byte 12, which is where class A 'ends', the JVM broke rule 2 and stuck a short and a byte before a long, to save 3 out of 4 bytes that would otherwise have been wasted.

Memory layout of arrays

Arrays have an extra header field that contain the value of the 'length' variable. The array elements follow, and the arrays, as any regular objects, are also aligned to an 8 bytes boundary.

Here is the layout of a byte array with 3 elements:

[HEADER:  12 bytes] 12
[[0]:      1 byte ] 13
[[1]:      1 byte ] 14
[[2]:      1 byte ] 15
[padding:  1 byte ] 16

And here is the layout of a long array with 3 elements:

[HEADER:  12 bytes] 12
[padding:  4 bytes] 16
[[0]:      8 bytes] 24
[[1]:      8 bytes] 32
[[2]:      8 bytes] 40

Memory layout of inner classes

Non-static inner classes have an extra 'hidden' field that holds a reference to the outer class. This field is a regular reference and it follows the rule of the in memory layout of references. Inner classes, for this reason, have an extra 4 bytes cost.

Final thoughts

We have learned how to calculate the shallow size of any Java object in the 32 bit Sun JVM. Knowing how memory is structured can help you understand how much memory is used by instances of your classes.

神奇的异或

熟练理解和掌握位操作，在有些情况下能使程序的效率提高不少，当然代码的可读性就降低 了，维护也比较困难。相比于与操作(&),或操作(|)，异或操作(^)显得更难以理解，甚至看 不出它有什么妙用。下面列举一些用到异或操作的问题，或许能从中学到一些新的东西。

1. 不使用中间变量，交换两个数的值

     //version 1
     void swap(int &a,int &b){
         a ^= b;
         b ^= a;
         a ^= b;
     }
   
     //version 2
     void swap(int &a,int &b){
         a -= b;
         b += a;
         a = b-a;
     }
   
   
   /*注意这两个版本都有个bug，当a，b指向同一个对象时，会变成0。而且有文章指出，版本
   1位操作未必比使用中间变量的性能好，再考虑到可读性，那这样的代码就更不推荐了。
   姑且就当作一种娱乐吧。
   */
   

2. 有一组数字,每个数字都不相同，放在大小为N-1的数组里，数字的范围是1-N，找出丢失 的那个数。只能申请少于O(N)的常数空间，时间复杂度O(n)。如果丢失两个数呢？

   /*容易想到的O(n)算法是将所有的数相加，然后用N(N+1)/2去减，得到的差就是丢失的那个
   数。但问题在于所有的数之和可能会溢出。还有人说用 sum(array[i]-i),实际上这也没
   有解决可能的溢出问题。
   
   异或可以解决这个问题。将所有的数array[i]异或得到k，k再与1到N所有的数异或得到
   k',则k'就是丢失的那个数a。
   
   如果丢失两个数，同样用异或的方法。假设丢失的是a,b,则 k' = a^b,k'获得方法如上。
   定义lowbit(i)函数,返回i的二进制表示中不为0的最低位，则a，b在lowbit(k')位上肯定
   是不同的。将原数组array[1..N-1]中lowbit(k')位为1的数异或得到k'',再用k''与1-N中
   lowbit(k')位为1的数异或得到k''',则k'''为a,b其中的一个，再用k''' ^ k'得到另一个。
   */
   
     //查找唯一丢失的数
     //array 长度为N-1，值范围为1-N，数组中每个数都不相同
     int findmiss(int *array,int N){
         int a; // result
         int i;
         a = 0;
         for(i=0;i<N-1;i++)
             a ^= array[i];
         for(i=1;i<=N;i++)
             a ^= i;
         return a;
     }
     
     //lowbit 的实现
     int lowbit(int i){
         return i & -i;
     }
     
     //查找丢失的两个数
     //array 长度为N-2，值范围为1-N，数组中每个数都不相同
     //a,b为丢失的数
     void findmiss2(int *array,int N,int *a,int *b){
         int i,k,lb;
         k = 0;
         *a = 0,*b = 0;
         for(i=0;i<N-2;i++)
             k ^= array[i];
         /* after this recurse, k=a^b */
         for(i=1;i<=N;i++)
             k ^= i;
         lb = lowbit(k); 
         for(i=0;i<N-2;i++){
             if(array[i] & lb != 0)
                 *a ^= array[i];
             else
                 *b ^= array[i];
         }
         for(i=1;i<=N;i++){
             if(i & lb != 0)
                 *a ^= i;
             else
                 *b ^= i;
         }
         return ;
     }
   

3. n个数中有且仅有一个数出现了奇数次（其他数都出现了偶数次），如果用线性时间常数 空间找出这个数？如果是两个数出现了奇数次呢？如果是三个数呢？或者是k个数？

   /*如果稍微想一想，就会发现这题与题目2有很多相似之处。所以下面的解法也很类似。
     
   第一问：有且仅有一个数出现奇数次，对数组n个数从头到尾异或一遍，得到的值即为要
   求的那个数。
   
   第二问：如果有两个数出现了奇数次。同题目2，先异或所有元素得到k，取lowbit(k),
   按照lowbit(k)将原数组分为两组，对这两组分别求异或，就得到要求的两个数。
   
   第三问: 如果是三个数。这一问就很难了，即使知道应该从异或这个角度去考虑，也很难
   想出好方法。当然，总有牛人会想出好方法，关键是找出第一个来，然后借助第二问结论
   求另外两个。为了不影响意思的理解，转载原文如下:
   
   // Let s = a ^ b ^ c.  We know that s not in (a, b, c), 
   // since if s == a, say, then b ^ c == 0 and b == c.  
   // Let f(x) be the lowest bit where x differs from s.  
   // The algorithm computes flips = f(a) ^ f(b) ^ f(c), 
   // since the numbers appearing an even number of times cancel.  
   // The variable flips has parity 1, so it is non-zero, 
   // and lowbit(flips) is a bit where one or three of a, b, c 
   // differ from s.  It can't be three(这个需要仔细想想), however, so the final 
   // exclusive-or includes exactly one of a, b, c.
   
   第四问：如果是k个数。从第3问我们可以发现，用类似的方法总可以找出第一个来，然
   后将问题转化为k-1规模的，则可以递归解决。复杂度为O(k^2*n).
   */
   
     // get lowest different bit
     int lowbit(int x){
         return x & ~(x - 1);
     }
     
     // Given an array of n integers, such that each number 
     // in the array appears exactly twice, except for two 
     // numbers (say a and b) which appear exactly once.
     // 
     // In O(n) time and O(1) space find a and b. 
     // e.g.
     // { 2 3 3 2 4 6 4 7 8 8 }  ---> a/b = { 6 7}
     void Find2(int seq[], int n, int& a, int& b)
     {
         ////XOR
         int xors = 0;
         for(int i = 0; i < n; i++)
             xors ^= seq[i];
     
         ////get different bit
         int diff = lowbit(xors);
     
         ////
         a = 0;
         b = 0;
         for(int i = 0; i < n; i++){
             if(diff & seq[i])
                 a ^= seq[i];
             else
                 b ^= seq[i];
         }
     }
     
     
     // Given an array of n integers, such that each number 
     // in the array appears exactly twice, except for three 
     // numbers (say a, b and c) which appear exactly once.
     // 
     // In O(n) time and O(1) space find a,b and c. 
     // e.g.
     // { 2 3 3 2 4 6 4 7 8 8 1 }  ---> a/b = { 6 7 1}
     
     
     // Let s = a ^ b ^ c.  We know that s not in (a, b, c), 
     // since if s == a, say, then b ^ c == 0 and b == c.  
     // Let f(x) be the lowest bit where x differs from s.  
     // The algorithm computes flips = f(a) ^ f(b) ^ f(c), 
     // since the numbers appearing an even number of times cancel.  
     // The variable flips has parity 1, so it is non-zero, 
     // and lowbit(flips) is a bit where one or three of a, b, c 
     // differ from s.  It can't be three, however, so the final 
     // exclusive-or includes exactly one of a, b, c.
     
     void Find3(int seq[], int n, int& a, int& b, int& c)
     {
         ////XOR
         int xors = 0;
         for(int i = 0; i < n; i++)
             xors ^= seq[i];
     
         ////
         int flips = 0;
         for(int i = 0; i < n; i++)
             flips ^= lowbit(xors ^ seq[i]);
         flips = lowbit(flips);
     
         ////get one of three
         a = 0;
         for(int i = 0; i < n; i++){
             if(lowbit(seq[i] ^ xors) == flips)
                 a ^= seq[i];
         }
     
         ////swap a with the last element of seq
         for(int i = 0; i < n; i++){
             if(a == seq[i]){
                 int temp = seq[i];
                 seq[i] = seq[n - 1];
                 seq[n - 1] = temp;
             }
         }
     
         ////call Find2() to get b and c
         Find2(seq, n - 1, b, c);
     }
   

4. n个数中只有一个数出现了一次，其他的数出现了3次，如何用O(n)的时间复杂度，常数空 间的算法找出这个数？如果这个数出现两次呢？

   /*考虑3进制。利用3进制的异或：  
   1 xor 0 = 1
   1 xor 1 = 2
   1 xor 2 = 0
   2 xor 0 = 2
   2 xor 2 = 1
   0 xor 0 = 0
   
   详见参考资料[4]
   */
   

5. nim游戏.有若干堆石子，每次可以选择一堆石子，从这堆石子中拿走任意数量的石 子，也就是至少拿走一个，最多把这堆石子全部拿走，两人轮流取，谁取走最后一个石子 谁就赢.问是否先手必胜。

   假设有n堆石子，数量分别为a1,a2,a3...an，那么如果石子的异或和不是0， 那么先手必
   胜也就是a1^a2^...^an != 0,那么先手必胜。看起来很神奇吧，感觉很复杂的游戏居然用
   异或就给解决了。是不是觉得自己很笨，怎么没有想到？没啥关系，早在16世纪，nim游
   戏就已经提出来了，但是到了1901年才被哈佛的一个教授解决，说明这世上跟我一样笨的
   人还是很多的。详细的讨论可以看 "http://en.wikipedia.org/wiki/Nim" .那先手要怎么走呢（想想怎么使异或变为0）？
   

参考资料

1. http://www.isnowfy.com/nim-game-and-numeral-system/
2. http://blog.csdn.net/yysdsyl/article/details/4289828
3. http://daiyanfei.blog.51cto.com/698782/215134/
4. http://www.liyaos.com/blog/findtwicenumber/