用 C 实现一个变长数组中的技巧

在云风的博客 用 C 实现一个变长数组中提到:

"一般的 vector 的实现，需要记录三个数据：数据空间的地址，空间大小，数组里已存在的元素个数。
....
我这几天在写代码时发现，如果你遵照空间加倍这个策略来运作，其实并不需要三个变量来维持 vector 结构，两个就够了。那个表识容量大小的变量是多余的。:D"

有如下代码:

struct vector {
  int *data;
  int size;
};

void
vector_expand(struct vector *v, int s)
{
  int new_size=v->size + s;
  if ((new_size ^ v->size) > v->size) {
     v->data=(int *)realloc(v->data,sizeof(int)*(new_size * 2 - 1));
  }
}

一开始不理解, 后来想通了, 记录一下:
capacity表示分配的空间容量.
binary_len(i) 表示i的2进制位的长度.
那么
if ((new_size ^ v->size) > v->size) 这句等价于
if (binary_len(new_size) > binary_len(v->size))

为什么等价？
如果len(new_size) = len(v-size), 最高位1被异或掉了,
那么结果的位数就会小于v->size的位数.

这样,那句话的`深层'含义是说只有当new_size的(2进制位)长度比size的增加了,
才有可能发生new_size > capacity.

因为有个隐含的前置条件或者循环不变式:
capacity = last_size * 2 - 1 (其中last_size是上一次分配时已存在元素的个数)
只要size没有发生位数变化, 是不可能超过capacity的.

举个边界情况的例子:
假如上一次分配内存时, size = (10000), 则capacity = (11111),
那么new_size只要还是5位数, 异或结果就会小于 v->size. 就还不需要分配空间.