1. 內(nèi)容##
本章講了一些代碼調(diào)優(yōu)的技巧
1.1 一些調(diào)優(yōu)方法###
整數(shù)取模(取模運(yùn)算時(shí)間大于加減法執(zhí)行時(shí)間)，k=k%n 可以替換為 if(k>=n) k=k-n;
函數(shù)、宏吨凑、和內(nèi)聯(lián)代碼
順序搜索,采用“哨兵” 讓循環(huán)體不用 每次都判斷邊界淋纲。從而增加了運(yùn)行速度
進(jìn)行循環(huán)展開增热，替換自增堪澎。
1.2 對(duì)于二分的優(yōu)化###
對(duì)二分進(jìn)行優(yōu)化雖然效率提高不少麦萤，但也應(yīng)該看到可讀性變得很差炼吴，維護(hù)起來也比較麻煩本鸣。
2. 習(xí)題##
7.給定一個(gè)非常長(zhǎng)的字節(jié)序列（假設(shè)有十億或萬億），如何高效的統(tǒng)計(jì)1的個(gè)數(shù)?###
1.算法一：假設(shè)x當(dāng)前為一個(gè)奇數(shù)硅蹦，則x=*1(＊代表若干個(gè)位)荣德，則x-1=*0(＊部分不變)闷煤， 相與的結(jié)果就是末位的1消失。假設(shè)x當(dāng)前為一個(gè)大于0的偶數(shù)涮瞻，則x=*1&0(＊代表若干個(gè)位,&代表若干個(gè)0)鲤拿，則x-1=*0%1(其中％代表若干個(gè)1，其數(shù)量與上面的&代表的0的數(shù)量相等)署咽，相與的結(jié)果為*0&0,即后面幾位全部變成0近顷。 綜上，x&(x－1)的結(jié)果就是把x的最低位的1變成0.所以下面的函數(shù)執(zhí)行的次數(shù)為x中1的個(gè)數(shù)宁否。
int OneCount(unsigned int x)
{
int count=0;
for( ; x>0; count++) x &= (x-1);
return count;
}
2.算法二: 查表法
const int idx[256]={0,1,1,……,8}//0~255中含1的個(gè)數(shù)
int OneCount(unsigned int x)
{
int count=0;
for(; x>0; x>>=8)
count+=idx[x&255];
return count;
}
8.如何使用哨兵來找出數(shù)組中的最大元素窒升？###
關(guān)鍵是總是設(shè)arr[n]為當(dāng)前找到的最大值，及時(shí)去更新arr[n].
i=0
while(i < n)
max=arr[i]
arr[n]=max //哨兵
while(arr[i]<max)
i++
9.y = a(n) * x^n + a(n-1) * x^(n-1) + ... + a1 * x + a0 的計(jì)算所需的次數(shù)慕匠？###
1.需要2n次
a[n+1] // contains a[0]...a[n]
y=a[0]
xi=1
i=1
while( i<=n )
xi*=x
y+= a[i]*xi
2.n次－－－by horner
a[n+1] // contains a[0]...a[n]
y=a[n]
for i in [1,n]
y=y*x+a[n-i]
