/**/ /* ?base.h：基本操作的位運算實現? */ ??
#ifndef?BASE_H???
#define ?BASE_H???
#define ?word???int???
#define ?uword??unsigned?int???
/**/ /* ?將最右側的1位改成0位? */ ??
#define ?right1to0(x)??((x)&((x)-1))???
/**/ /* ?向右傳播最右側的1位? */ ??
#define ?right1torig(x)??((x)|((x)-1))???
/**/ /* ?將最右側的連續1位串改成0位串? */ ??
#define ?right1sto0s(x)??(((x)|(x)-1)+1?&?(x))???
/**/ /* ?檢查無符號整數x是否為2的冪，注意&的優先級低于==，需要括號? */ ??
#define ?powof2u(x)??(((x)&((x)-1))==0)???
/**/ /* ?檢查無符號整數x是否為2**n-1的形式? */ ??
#define ?pow2sub1u(x)??(((x)&((x)+1))==0)???
/**/ /* ?檢查無符號整數x是否為2**j-2**k形式? */ ??
#define ?pow2subpow2u(x)??((((x)|(x)-1)+1?&?(x))==0)???
??
/**/ /* ?下列掩碼直接析出字中指定的位? */ ??
/**/ /* ?析出最右側的1位? */ ??
#define ?right1(x)??((x)?&?-(x))???
/**/ /* ?析出最右側的0位? */ ??
#define ?right0(x)??(~(x)&((x)+1))???
/**/ /* ?析出后綴0? */ ??
#define ?suffix0(x)??(((x)&-(x))-1)???
/**/ /* ?析出最右側的1位和后綴0(即后綴100)? */ ??
#define ?suffix10s0(x)??((x)?^?(x)-1)???
/**/ /* ?下列掩碼與字做&運算，可以析出字中指定的字段? */ ??
/**/ /* ?析出高階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位，它右側有offset位? */ ??
#define ?mid_ones(width,offset)?????\???
????????( ~ ( - 1 << (width) + (offset))? & ?( - 1 << (offset)))???
??
/**/ /* ?對無符號整數x，求比x大且與x中的位1個數相同的下一個整數：??
????例如對nnn0?1111?0000，則下一個整數為nnn1?0000?01111。??
????可以用這個函數來遍歷一個集合的所有子集? */ ??
#define ?nextsame1u(x)??(right1(x)+(x)?|??????\???
??????(((x) ^ right1(x) + (x)) >> 2 ) / right1(x))???
/**/ /* ?字的絕對值函數：注意x>>31為0或-1，而x^0=x，x^-1=~x? */ ??
#define ?abs(x)??(((x)^((x)>>31))-((x)>>31))???
/**/ /* ?絕對值的負值? */ ??
#define ?nabs(x)??(((x)>>31)-((x)^((x)>>31)))????
/**/ /* ?符號擴展：將第7位向左傳播(位編號從0開始)? */ ??
#define ?prop7thtolef(x)??((((x)?&?0x000000FF)?^?0x00000080)-0x00000080)???
/**/ /* ?對無符號整數實現算術右移：也可用更簡單的((signed)(x)>>n)? */ ??
#define ?arithrshiftu(x,n)??((((x)^0x80000000)>>(n))-(0x80000000>>(n)))????????
/**/ /* ?對有符號整數實現邏輯右移：也可用更簡單的((unsigned)(x)>>n)? */ ??
#define ?logicrshift(x,n)??((((x)^0x80000000)>>(n))+(1<<31-(n)))????
/**/ /* ?符號函數：x>0返回1，x=0返回0，x<0返回-1? */ ??
#define ?sign(x)??(((x)>0)-((x)<0))???
/**/ /* ?三值比較函數：x>y返回1，x=y返回0，x<y返回-1? */ ??
#define ?cmp(x,y)??(((x)>(y))-((x)<(y)))???
/**/ /* ??符號傳遞函數：返回采用y的符號后的x? */ ??
#define ?copysign(x,y)??((abs(x)^((y)>>31))-((y)>>31))????
/**/ /* ?比較謂詞：帶符號整數? */ ??
#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)???
/**/ /* ?比較謂詞：無符號整數? */ ????????
#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)???
/**/ /* ?溢出檢測：帶符號運算? */ ??
#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)???
/**/ /* ?溢出檢測：無符號運算? */ ??
#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)???
/**/ /* ?循環移位：帶符號整數? */ ??
/**/ /* ?循環左移n位? */ ??
#define ?rotlshift(x,n)??((x)<<(n)?|?(unsigned)(x)>>32-(n))???
/**/ /* ?循環右移n位? */ ??
#define ?rotrshift(x,n)??((unsigned)(x)>>(n)?|?(x)<<32-(n))???
/**/ /* ?循環移位：無符號整數? */ ??
#define ?rotlshiftu(x,n)??((x)<<(n)?|?(x)>>32-(n))???
#define ?rotrshiftu(x,n)??((x)>>(n)?|?(x)<<32-(n))???
/**/ /* ?正差函數：x>=y時返回x-y，x<y時返回0。注意&優先級高于^，無需要括號? */ ??
#define ?doz(x,y)??((x)-(y)&~((x)-(y)^((x)^(y))&((x)-(y)^(x)))>>31)???
/**/ /* ?大值函數? */ ??
#define ?max(x,y)??((y)+doz(x,y))???
/**/ /* ?小值函數? */ ??
#define ?min(x,y)??((x)-doz(x,y))???
/**/ /* ?下面是無符號版本? */ ??
#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 )???
/**/ /* ?根據掩碼來交換變量的相應字段：??
????當m的第i位為1時，交換x,y的第i位；當m的第i位為0時，保留x,y的第i位不變?? */ ??
#define ?swapbits(x,y,m)?????\???
???? do ? {?x = x ^ y;?y = y ^ (x & (m));?x = x ^ y;?} ? while ( 0 )???????
/**/ /* ?2個常量的循環賦值：當x為a時賦值b，當x為b時賦值a? */ ??
#define ?rottwo(x,a,b)??do{?x=(a)^(b)^x;?}while(0)???
/**/ /* ?3個常量的循環賦值? */ ??
#define ?rotthree(x,a,b,c)?????\???
???? do {?x = ( - (x == c) & (a - c)) + ( - (x == a) & (b - c)) + c;?} while ( 0 )???
#endif ?