C++實(shí)現(xiàn)LeetCode(190.顛倒二進(jìn)制位)

第C++實(shí)現(xiàn)LeetCode(190.顛倒二進(jìn)制位)[LeetCode]190.ReverseBits顛倒二進(jìn)制位

Reversebitsofagiven32bitsunsignedinteger.

Example1:

Input:00000010100101000001111010011100

Output:00111001011110000010100101000000

Explanation:Theinputbinarystring00000010100101000001111010011100representstheunsignedinteger43261596,soreturn964176192whichitsbinaryrepresentationis00111001011110000010100101000000.

Example2:

Input:11111111111111111111111111111101

Output:10111111111111111111111111111111

Explanation:Theinputbinarystring11111111111111111111111111111101representstheunsignedinteger4294967293,soreturn3221225471whichitsbinaryrepresentationis10101111110010110010011101101001.

Note:

NotethatinsomelanguagessuchasJava,thereisnounsignedintegertype.Inthiscase,bothinputandoutputwillbegivenassignedintegertypeandshouldnotaffectyourimplementation,astheinternalbinaryrepresentationoftheintegeristhesamewhetheritissignedorunsigned.

InJava,thecompilerrepresentsthesignedintegersusing2'scomplementnotation.Therefore,inExample2abovetheinputrepresentsthesignedinteger-3andtheoutputrepresentsthesignedinteger-1073741825.

Followup:

Ifthisfunctioniscalledmanytimes,howwouldyouoptimizeit

Credits:

Specialthanksto@tsforaddingthisproblemandcreatingalltestcases.

這道題又是在考察位操作BitOperation，LeetCode中有關(guān)位操作的題也有不少，比如RepeatedDNASequences，SingleNumber,SingleNumberII，和GreyCode等等。跟上面那些題比起來，這道題簡直不能再簡單了，我們只需要把要翻轉(zhuǎn)的數(shù)從右向左一位位的取出來，如果取出來的是1，將結(jié)果res左移一位并且加上1；如果取出來的是0，將結(jié)果res左移一位，然后將n右移一位即可，參見代碼如下：

解法一：

classSolution{

public:

uint32_treverseBits(uint32_tn){

uint32_tres=0;

for(inti=0;i++i){

if(n1==1){

res=(res1)+1;

}else{

res=res1;

n=n1;

returnres;

};

我們可以簡化上面的代碼，去掉if...else...結(jié)構(gòu)，可以結(jié)果res左移一位，然后再判斷n的最低位是否為1，是的話那么結(jié)果res加上1，然后將n右移一位即可，代碼如下：

解法二：

classSolution{

public:

uint32_treverseBits(uint32_tn){

uint32_tres=0;

for(inti=0;i++i){

res=1;

if((n1)==1)++res;

n=1;

returnres;

};

我們繼續(xù)簡化上面的解法，將if判斷句直接揉進(jìn)去，通過‘或'上一個(gè)n的最低位即可，用n‘與'1提取最低位，然后將n右移一位即可，代碼如下：

解法三：

classSolution{

public:

uint32_treverseBits(uint32_tn){

uint32_tres=0;

for(inti=0;i++i){

res=(res1)|(n1);

n=1;

returnres;

};

博主還能進(jìn)一步簡化，這里不更新n的值，而是直接將n右移i位，然后通過‘與'1來提取出該位，加到左移一位后的結(jié)果res中即可，參加代碼如下：

解法四：

classSolution{

public:

uint32_treverseBits(uint32_tn){

uint32_tres=0;

for(inti=0;i++i){

res=(res1)+(ni1);

returnres;

};

我們也可以換一種角度來做，首先將n右移i位，然后通過‘與'1來提取出該位，然后將其左移(32-i)位，然后‘或'上結(jié)果res，就是其顛倒后應(yīng)該在的位置，參見代碼如下：

解法五：

classSolution{

public:

uint32_treverseBits(uint32_tn){

uint32_tres=0;

for(inti=0;i++i){

res|=((ni)1)(31-i);

returnres;

};

Github同步地址：

/grandyang/leetcode/issues/190

類似題目：

Numberof1Bits

ReverseInteger

參考資料：

/problems/reverse-bits/

/problems/reverse-bits/discuss/54938/A-short-simple-Java-solution

/problems/reverse-bits/discuss/54772/The-concise-C++-solution(9ms)

/problems/reverse-bits/discuss/54741/O(1)-bit-operation-C++-solution-(8ms)

/problems/reverse-bits