C++实现LeetCode(190.颠倒二进制位)

2024-08-16 20:45:38

[LeetCode] 190. Reverse Bits 颠倒二进制位

Reverse bits of a given 32 bits unsigned integer.

Example 1:

Input: 00000010100101000001111010011100
Output: 00111001011110000010100101000000
Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.

Example 2:

Input: 11111111111111111111111111111101
Output: 10111111111111111111111111111111
Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10101111110010110010011101101001.

Note:

Note that in some languages such as Java, there is no unsigned integer type. In this case, both input and output will be given as signed integer type and should not affect your implementation, as the internal binary representation of the integer is the same whether it is signed or unsigned.
In Java, the compiler represents the signed integers using 2's complement notation. Therefore, in Example 2 above the input represents the signed integer -3 and the output represents the signed integer -1073741825.

Follow up:

If this function is called many times, how would you optimize it?

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

这道题又是在考察位操作 Bit Operation，LeetCode 中有关位操作的题也有不少，比如 Repeated DNA Sequences，Single Number, Single Number II ，和 Grey Code 等等。跟上面那些题比起来，这道题简直不能再简单了，我们只需要把要翻转的数从右向左一位位的取出来，如果取出来的是1，将结果 res 左移一位并且加上1；如果取出来的是0，将结果 res 左移一位，然后将n右移一位即可，参见代码如下：

解法一：

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t res = 0;
        for (int i = 0; i < 32; ++i) {
            if (n & 1 == 1) {
                res = (res << 1) + 1;
            } else {
                res = res << 1;
            }
            n = n >> 1;
        }
        return res;
    }
};

我们可以简化上面的代码，去掉 if...else... 结构，可以结果 res 左移一位，然后再判断n的最低位是否为1，是的话那么结果 res 加上1，然后将n右移一位即可，代码如下：

解法二：

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t res = 0;
        for (int i = 0; i < 32; ++i) {
            res <<= 1;
            if ((n & 1) == 1) ++res;
            n >>= 1;
        }
        return res;
    }
};

我们继续简化上面的解法，将 if 判断句直接揉进去，通过 ‘或' 上一个n的最低位即可，用n ‘与' 1提取最低位，然后将n右移一位即可，代码如下：

解法三：

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t res = 0;
        for (int i = 0; i < 32; ++i) {
            res = (res << 1) | (n & 1);
            n >>= 1;
        }
        return res;
    }
};

博主还能进一步简化，这里不更新n的值，而是直接将n右移i位，然后通过 ‘与' 1来提取出该位，加到左移一位后的结果 res 中即可，参加代码如下：

解法四：

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t res = 0;
        for (int i = 0; i < 32; ++i) {
            res = (res << 1) + (n >> i & 1);
        }
        return res;
    }
};

我们也可以换一种角度来做，首先将n右移i位，然后通过 ‘与' 1来提取出该位，然后将其左移 (32 - i) 位，然后 ‘或' 上结果 res，就是其颠倒后应该在的位置，参见代码如下：

解法五：

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t res = 0;
        for (int i = 0; i < 32; ++i) {
            res |= ((n >> i) & 1) << (31 - i);
        }
        return res;
    }
};

Github 同步地址：

https://github.com/grandyang/leetcode/issues/190

类似题目：

Number of 1 Bits

Reverse Integer

参考资料：

https://leetcode.com/problems/reverse-bits/

https://leetcode.com/problems/reverse-bits/discuss/54938/A-short-simple-Java-solution

https://leetcode.com/problems/reverse-bits/discuss/54772/The-concise-C++-solution(9ms)

https://leetcode.com/problems/reverse-bits/discuss/54741/O(1)-bit-operation-C++-solution-(8ms)

https://leetcode.com/problems/reverse-bits/discuss/54738/Sharing-my-2ms-Java-Solution-with-Explanation

https://leetcode.com/problems/reverse-bits/discuss/54873/Java-two-methods-using-String-or-bit-operation-6ms-and-2ms-easy-understand

到此这篇关于C++实现LeetCode(190.颠倒二进制位)的文章就介绍到这了,更多相关C++实现颠倒二进制位内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

C++实现LeetCode(557.翻转字符串中的单词之三)

[LeetCode] 557.Reverse Words in a String III 翻转字符串中的单词之三 Given a string, you need to reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order. Example 1: Input: "Let's take LeetCode conte
C++实现LeetCode(188.买卖股票的最佳时间之四)

[LeetCode] 188.Best Time to Buy and Sell Stock IV 买卖股票的最佳时间之四 Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete at most k transactions. Note: You m
SQL实现LeetCode(182.重复的邮箱)

[LeetCode] 182.Duplicate Emails 重复的邮箱 Write a SQL query to find all duplicate emails in a table named Person. +----+---------+ | Id | Email | +----+---------+ | 1 | a@b.com | | 2 | c@d.com | | 3 | a@b.com | +----+---------+ For example, your que
C++实现LeetCode(186.翻转字符串中的单词之二)

[LeetCode] 186. Reverse Words in a String II 翻转字符串中的单词之二 Given an input string , reverse the string word by word. Example: Input: ["t","h","e"," ","s","k","y"," ","i&qu
C++实现LeetCode(309.买股票的最佳时间含冷冻期)

[LeetCode] 309.Best Time to Buy and Sell Stock with Cooldown 买股票的最佳时间含冷冻期 Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete as many transactions as
SQL实现LeetCode(185.系里前三高薪水)

[LeetCode] 185.Department Top Three Salaries 系里前三高薪水 The Employee table holds all employees. Every employee has an Id, and there is also a column for the department Id. +----+-------+--------+--------------+ | Id | Name | Salary | DepartmentId | +--
SQL实现LeetCode(183.从未下单订购的顾客)

[LeetCode] 183.Customers Who Never Order 从未下单订购的顾客 Suppose that a website contains two tables, the Customers table and the Orders table. Write a SQL query to find all customers who never order anything. Table: Customers. +----+-------+ | Id | Name |
SQL实现LeetCode(184.系里最高薪水)

[LeetCode] 184.Department Highest Salary 系里最高薪水 The Employee table holds all employees. Every employee has an Id, a salary, and there is also a column for the department Id. +----+-------+--------+--------------+ | Id | Name | Salary | DepartmentId
C++实现LeetCode(190.颠倒二进制位)

[LeetCode] 190. Reverse Bits 颠倒二进制位 Reverse bits of a given 32 bits unsigned integer. Example 1: Input: 00000010100101000001111010011100 Output: 00111001011110000010100101000000 Explanation: The input binary string 00000010100101000001111010011100 re
C++实现LeetCode(156.二叉树的上下颠倒)

[LeetCode] 156. Binary Tree Upside Down 二叉树的上下颠倒 Given a binary tree where all the right nodes are either leaf nodes with a sibling (a left node that shares the same parent node) or empty, flip it upside down and turn it into a tree where the origina
C++实现LeetCode(52.N皇后问题之二)

[LeetCode] 52. N-Queens II N皇后问题之二 The n-queens puzzle is the problem of placing nqueens on an n×n chessboard such that no two queens attack each other. Given an integer n, return the number of distinct solutions to the n-queens puzzle. Example: Inpu
Pipes实现LeetCode(192.单词频率)

[LeetCode] 192.Word Frequency 单词频率 Write a bash script to calculate the frequency of each word in a text file words.txt. For simplicity sake, you may assume: words.txt contains only lowercase characters and space ' ' characters. Each word must consis
LeetCode -- Path Sum III分析及实现方法

LeetCode -- Path Sum III分析及实现方法题目描述: You are given a binary tree in which each node contains an integer value. Find the number of paths that sum to a given value. The path does not need to start or end at the root or a leaf, but it must go downwards
C语言实现颠倒栈的方法

本文实例讲述了C语言实现颠倒栈的方法,很实用的技巧.分享给大家供大家参考之用. 具体实现方法如下: #include <iostream> #include <iterator> #include <algorithm> #include <vector> #include <stack> using namespace std; void initializeStack(stack<int> &st) { for(int i
基于Java实现杨辉三角 LeetCode Pascal's Triangle

Pascal's Triangle Given numRows, generate the first numRows of Pascal's triangle. For example, given numRows = 5, Return [ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ] 这道题比较简单, 杨辉三角, 可以用这一列的元素等于它头顶两元素的和来求. 数学扎实的人会看出, 其实每一列都是数学里的排列组合, 第4行, 可以用 C30 =
php识别翻转iphone拍摄的颠倒图片

用iphone横向拍摄并上传的图片往往是向左或向右90度侧向显示的,本文介绍如何用php识别并且翻转图片到正确位置. ps : 此方法只能判断一些手机相机拍摄的图片位置颠倒代码: // 首先用这个函数读取图片的一些头信息 // 原理就是在头信息中取出图片的位置信息并且根据位置信息对图片做出调整 // 此函数只能处理jpeg 与 tiff 的图片格式 $exif = exif_read_data ($url,0,true); if(isset($exif['IFD0']['Orientatio
vscode中配置LeetCode插件的教程(愉快刷题)

大家好,今早在B站看到up主的vscode里藏了leetcode插件,这才知道原来还有这款神器.但是没想到在用的时候遇到了一些麻烦,花了一点时间才解决.所以写这篇文章除了给大家安利这个好用的插件之外,也是为了帮助更多的同学避免踩坑. 简介vscode vscode在工业界鼎鼎大名,被誉为微软少有的拿得出手的精品(逃).原本是不想过多赘述的,但是鉴于许多粉丝还是正在上学的萌新,所以花点笔墨简单介绍一下. vscode是微软开发的编辑器,严格说起来它并不是一个IDE,只是一个编辑器.但是由于它支持嵌
vscode+leetcode环境配置方法

前言之前安装anaconda3的时候,选择了同时安装vscode,但从来没有正式去接触过它.最近,偶然想到看看leetcode,发现在vscode上搞leetcode很方便,于是就开始倒腾起来了. vscode配置如何安装我就不详述了,win/ubuntu下的安装可参见我的博客: vscode+python+c++ 我现在的vscode的版本是:1.43.1 需要安装的插件有: anaconda extension pack: 支持非python官方的三方库code runner:F5快捷运

C++实现LeetCode(190.颠倒二进制位)

[LeetCode] 190. Reverse Bits 颠倒二进制位

相关推荐

随机推荐