/**/ /* ?base.h：基本操作的位運(yùn)算實(shí)現(xiàn)? */ ??
#ifndef?BASE_H???
#define ?BASE_H???
#define ?word???int???
#define ?uword??unsigned?int???
/**/ /* ?將最右側(cè)的1位改成0位? */ ??
#define ?right1to0(x)??((x)&((x)-1))???
/**/ /* ?向右傳播最右側(cè)的1位? */ ??
#define ?right1torig(x)??((x)|((x)-1))???
/**/ /* ?將最右側(cè)的連續(xù)1位串改成0位串? */ ??
#define ?right1sto0s(x)??(((x)|(x)-1)+1?&?(x))???
/**/ /* ?檢查無(wú)符號(hào)整數(shù)x是否為2的冪，注意&的優(yōu)先級(jí)低于==，需要括號(hào)? */ ??
#define ?powof2u(x)??(((x)&((x)-1))==0)???
/**/ /* ?檢查無(wú)符號(hào)整數(shù)x是否為2**n-1的形式? */ ??
#define ?pow2sub1u(x)??(((x)&((x)+1))==0)???
/**/ /* ?檢查無(wú)符號(hào)整數(shù)x是否為2**j-2**k形式? */ ??
#define ?pow2subpow2u(x)??((((x)|(x)-1)+1?&?(x))==0)???
??
/**/ /* ?下列掩碼直接析出字中指定的位? */ ??
/**/ /* ?析出最右側(cè)的1位? */ ??
#define ?right1(x)??((x)?&?-(x))???
/**/ /* ?析出最右側(cè)的0位? */ ??
#define ?right0(x)??(~(x)&((x)+1))???
/**/ /* ?析出后綴0? */ ??
#define ?suffix0(x)??(((x)&-(x))-1)???
/**/ /* ?析出最右側(cè)的1位和后綴0(即后綴100)? */ ??
#define ?suffix10s0(x)??((x)?^?(x)-1)???
/**/ /* ?下列掩碼與字做&運(yùn)算，可以析出字中指定的字段? */ ??
/**/ /* ?析出高階n位(注意n的值不能大于int型的寬度)? */ ??
#define ?high_ones(n)?(-1<<32-(n))???
/**/ /* ?析出低階n位? */ ??
#define ?low_ones(n)?(~(-1<<(n)))???
/**/ /* ?析出低階offset位和高階32-offset-width位? */ ??
#define ?mid_zeros(width,offset)????\???
????????( - 1 << (width) + (offset)? | ? ~ ( - 1 << (offset)))???????
/**/ /* ?析出中間width位，它右側(cè)有offset位? */ ??
#define ?mid_ones(width,offset)?????\???
????????( ~ ( - 1 << (width) + (offset))? & ?( - 1 << (offset)))???
??
/**/ /* ?對(duì)無(wú)符號(hào)整數(shù)x，求比x大且與x中的位1個(gè)數(shù)相同的下一個(gè)整數(shù)：??
????例如對(duì)nnn0?1111?0000，則下一個(gè)整數(shù)為nnn1?0000?01111。??
????可以用這個(gè)函數(shù)來(lái)遍歷一個(gè)集合的所有子集? */ ??
#define ?nextsame1u(x)??(right1(x)+(x)?|??????\???
??????(((x) ^ right1(x) + (x)) >> 2 ) / right1(x))???
/**/ /* ?字的絕對(duì)值函數(shù)：注意x>>31為0或-1，而x^0=x，x^-1=~x? */ ??
#define ?abs(x)??(((x)^((x)>>31))-((x)>>31))???
/**/ /* ?絕對(duì)值的負(fù)值? */ ??
#define ?nabs(x)??(((x)>>31)-((x)^((x)>>31)))????
/**/ /* ?符號(hào)擴(kuò)展：將第7位向左傳播(位編號(hào)從0開(kāi)始)? */ ??
#define ?prop7thtolef(x)??((((x)?&?0x000000FF)?^?0x00000080)-0x00000080)???
/**/ /* ?對(duì)無(wú)符號(hào)整數(shù)實(shí)現(xiàn)算術(shù)右移：也可用更簡(jiǎn)單的((signed)(x)>>n)? */ ??
#define ?arithrshiftu(x,n)??((((x)^0x80000000)>>(n))-(0x80000000>>(n)))????????
/**/ /* ?對(duì)有符號(hào)整數(shù)實(shí)現(xiàn)邏輯右移：也可用更簡(jiǎn)單的((unsigned)(x)>>n)? */ ??
#define ?logicrshift(x,n)??((((x)^0x80000000)>>(n))+(1<<31-(n)))????
/**/ /* ?符號(hào)函數(shù)：x>0返回1，x=0返回0，x<0返回-1? */ ??
#define ?sign(x)??(((x)>0)-((x)<0))???
/**/ /* ?三值比較函數(shù)：x>y返回1，x=y返回0，x<y返回-1? */ ??
#define ?cmp(x,y)??(((x)>(y))-((x)<(y)))???
/**/ /* ??符號(hào)傳遞函數(shù)：返回采用y的符號(hào)后的x? */ ??
#define ?copysign(x,y)??((abs(x)^((y)>>31))-((y)>>31))????
/**/ /* ?比較謂詞：帶符號(hào)整數(shù)? */ ??
#define ?equal(x,y)?????(~((x)-(y)|(y)-(x))>>31)???
#define ?noteq(x,y)?????(((x)-(y)|(y)-(x))>>31)???
#define ?less(x,y)??????((((x)^(y))?&?((x)-(y)^(x))?^?(x)-(y))>>31)???
#define ?larger(x,y)????((((y)^(x))?&?((y)-(x)^(y))?^?(y)-(x))>>31)???
#define ?lesseq(x,y)????((((x)|~(y))?&?((x)^(y)?|?~((y)-(x))))>>31)???
#define ?largereq(x,y)??((((y)|~(x))?&?((y)^(x)?|?~((x)-(y))))>>31)???
/**/ /* ?比較謂詞：無(wú)符號(hào)整數(shù)? */ ????????
#define ?equalu(x,y)?????(~((x)-(y)|(y)-(x))>>31)???
#define ?notequ(x,y)?????(((x)-(y)|(y)-(x))>>31)???
#define ?lessu(x,y)??????((~(x)?&?(y)?|?~((x)^(y))?&?(x)-(y))>>31)???
#define ?largeru(x,y)????((~(y)?&?(x)?|?~((y)^(x))?&?(y)-(x))>>31)???
#define ?lessequ(x,y)????(((~(x)|(y))?&?(((x)^(y))?|?~((y)-(x))))>>31)???
#define ?largerequ(x,y)??(((~(y)|(x))?&?(((y)^(x))?|?~((x)-(y))))>>31)???
/**/ /* ?溢出檢測(cè)：帶符號(hào)運(yùn)算? */ ??
#define ?addovf(x,y)??((~((x)^(y))&(((x)+(y))^(x)))>>31)???
#define ?subovf(x,y)??((((x)^(y))&(((x)-(y))^(x)))>>31)???
#define ?mulovf(x,y)??((y)<0?&&?(x)==0x80000000?||?(y)!=0?&&?(x)*(y)/(y)!=(x))???
#define ?divovf(x,y)??((y)==0?||?(x)==0x80000000?&&?(y)==-1)???
/**/ /* ?溢出檢測(cè)：無(wú)符號(hào)運(yùn)算? */ ??
#define ?addovfu(x,y)??(~(x)<(y))??/*?也可用less(~(x),y)?*/???
#define ?subovfu(x,y)??((x)<(y))???/*?也可用less(x,y)?*/???
#define ?mulovfu(x,y)??((y)!=0?&&?(x)?>?0xffffffff/(y))???
#define ?divovfu(x,y)??((y)==0)???
/**/ /* ?循環(huán)移位：帶符號(hào)整數(shù)? */ ??
/**/ /* ?循環(huán)左移n位? */ ??
#define ?rotlshift(x,n)??((x)<<(n)?|?(unsigned)(x)>>32-(n))???
/**/ /* ?循環(huán)右移n位? */ ??
#define ?rotrshift(x,n)??((unsigned)(x)>>(n)?|?(x)<<32-(n))???
/**/ /* ?循環(huán)移位：無(wú)符號(hào)整數(shù)? */ ??
#define ?rotlshiftu(x,n)??((x)<<(n)?|?(x)>>32-(n))???
#define ?rotrshiftu(x,n)??((x)>>(n)?|?(x)<<32-(n))???
/**/ /* ?正差函數(shù)：x>=y時(shí)返回x-y，x<y時(shí)返回0。注意&優(yōu)先級(jí)高于^，無(wú)需要括號(hào)? */ ??
#define ?doz(x,y)??((x)-(y)&~((x)-(y)^((x)^(y))&((x)-(y)^(x)))>>31)???
/**/ /* ?大值函數(shù)? */ ??
#define ?max(x,y)??((y)+doz(x,y))???
/**/ /* ?小值函數(shù)? */ ??
#define ?min(x,y)??((x)-doz(x,y))???
/**/ /* ?下面是無(wú)符號(hào)版本? */ ??
#define ?dozu(x,y)??((x)-(y)&?arithrshiftu(((x)|~(y))&((x)^(y)|~((x)-(y)))?,31))???
#define ?maxu(x,y)??((y)+dozu(x,y))???
#define ?minu(x,y)??((x)-dozu(x,y))???
/**/ /* ?交換變量的值? */ ??
#define ?swap(x,y)??????\???
???? do ? {?x = x ^ y;?y = y ^ x;?x = x ^ y;?} ? while ( 0 )???
/**/ /* ?根據(jù)掩碼來(lái)交換變量的相應(yīng)字段：??
????當(dāng)m的第i位為1時(shí)，交換x,y的第i位；當(dāng)m的第i位為0時(shí)，保留x,y的第i位不變?? */ ??
#define ?swapbits(x,y,m)?????\???
???? do ? {?x = x ^ y;?y = y ^ (x & (m));?x = x ^ y;?} ? while ( 0 )???????
/**/ /* ?2個(gè)常量的循環(huán)賦值：當(dāng)x為a時(shí)賦值b，當(dāng)x為b時(shí)賦值a? */ ??
#define ?rottwo(x,a,b)??do{?x=(a)^(b)^x;?}while(0)???
/**/ /* ?3個(gè)常量的循環(huán)賦值? */ ??
#define ?rotthree(x,a,b,c)?????\???
???? do {?x = ( - (x == c) & (a - c)) + ( - (x == a) & (b - c)) + c;?} while ( 0 )???
#endif ?