BitwiseEquations (SRM 430 Div2 500)
題目鏈接:http://www.topcoder.com/stat?c=problem_statement&pm=9921&rd=13521
x+y=x|y.
二進制加法1+0=1|0. 當而僅當x,y的二進制表示中,x的'1'位不與y的'1'對應,這個等式就成立.
所以,對于x中為1的位,y只能為0,對于x中為0的位,y相應位可以任意.
要求第k個y,很顯然,把k的二進制表示填充到x的0位中去,即可.
x+y=x|y.
二進制加法1+0=1|0. 當而僅當x,y的二進制表示中,x的'1'位不與y的'1'對應,這個等式就成立.
所以,對于x中為1的位,y只能為0,對于x中為0的位,y相應位可以任意.
要求第k個y,很顯然,把k的二進制表示填充到x的0位中去,即可.
???class?BitwiseEquations
??????????????{?
??????????????public:?
??????????????long?long?kthPlusOrSolution(int?_x,?int?k)?
??????????????????{?????????????????
??????????????????long?long?result;
??????????????????long?long?mask?=?1;
??????????????????long?long?x?=?_x;
??????????????????result?=?0;
??????????????????
??????????????????for(int?i=0;i<64&&k!=0;++i){
??????????????????????if((mask&x)==0){
????????????????????????????result|=((k&1)*mask);
????????????????????????????k>>=1;
??????????????????????}
??????????????????????mask<<=1;
??????????????????}?
??????????????????return?result;
??????????????}
}
??????????????{?
??????????????public:?
??????????????long?long?kthPlusOrSolution(int?_x,?int?k)?
??????????????????{?????????????????
??????????????????long?long?result;
??????????????????long?long?mask?=?1;
??????????????????long?long?x?=?_x;
??????????????????result?=?0;
??????????????????
??????????????????for(int?i=0;i<64&&k!=0;++i){
??????????????????????if((mask&x)==0){
????????????????????????????result|=((k&1)*mask);
????????????????????????????k>>=1;
??????????????????????}
??????????????????????mask<<=1;
??????????????????}?
??????????????????return?result;
??????????????}
}
posted on 2009-06-20 12:02 YZY 閱讀(922) 評論(0) 編輯 收藏 引用 所屬分類: Algorithm 、TopCoder