leetcode 位运算

本次题解包括

  • 89. Gray Code
  • 136 Single Number
  • 137 Single Number II
  • 190 Reverse Bits
  • 191 Number of 1 Bits
  • 201 Bitwise AND of Numbers Range
  • 260 Single Number III
  • 268 Missing Number

89. Gray Code

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

00 – 0
01 – 1
11 – 3
10 – 2

Note:
For a given n, a gray code sequence is not uniquely defined.

For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.

For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.

题目地址:leetcode Gray Code

题目大意:给定数字n,要你输出[0, 2^n – 1]格雷码。

思路:二进制x转化为格雷码的操作是  x ^ (x>> 1)

C++

Python

 

 

 

136. Single Number

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

题目地址:leetcode Single Number

题意:一个数组,除了一个元素出现一次外,其余每个元素都是出现两次,求出只出现过一次的元素

思路:用异或的性质,两次异或等于本身。so~

C++

Python

 

 


 

 

137. Single Number II

Given an array of integers, every element appears three times except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

题目地址:leetcode Single Number II

题意:一个数组,除了一个元素出现一次外,其余每个元素都是出现三次,求出只出现过一次的元素

思路:输入为Int有32位,对数组中每个数的各个位上进行相加,然后Mod3就是该位上只出现一次应该取的值。

C++

 

Python

python需要注意的是如果有负数出现,那么py最后进行移位不会认为它是负数,而是认为它是一个正数!

故需手动判断最高位是否为1,如果为1代表负数,求其补码(取反,末位+1)

 


 

190. Reverse Bits

Reverse bits of a given 32 bits unsigned integer.

For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as00111001011110000010100101000000).

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

传送门

题意:给定一个32位无符号整形,求把它的二进制颠倒顺序的结果。

思路:将ans左移并且加上n的最高位,然后将n右移,直到n为0。最后,需要左移上n前导0的个数。

 

 


 

 

191. Number of 1 Bits

Write a function that takes an unsigned integer and returns the number of ’1′ bits it has (also known as the Hamming weight).

For example, the 32-bit integer ’11′ has binary representation 00000000000000000000000000001011, so the function should return 3.

传送门

题意:给定一个32位整型,求它1 的个数

思路:

方法一

每次 &1 右移即可。

python:

其实上面一行代码只是下面这个的好看版。哈哈

C++

 

方法二:

先考虑一下我们从一个数减去1的时候发生了什么。

如: 0111 0000 – 1 = 0110 1111

就是从最低位到最低的1那一位全部取反。

接下来,我们看看n & (n-1)

0111 0000 & 0110 1111 =  0110 0000

我们看到,最后一个1变成了0,所以我们只需要O(m)次 ,m为1的个数就可以求出1的个数

C++

 

python

 

 

 


 

201. Bitwise AND of Numbers Range

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.

For example, given the range [5, 7], you should return 4.

传送门

题意:给定m和n,求从m连续 按位与到 n 的结果

思路:

一开始想,如果m的长度小于n,那结果必为0。只有一样长度的才需要进行与,所以写出如下代码:

虽然1A,但是实际上我们只需要求两个数字的二进制的最长公共前缀即可!

 

 

 

260. Single Number III

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

For example:

Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

Note:

  1. The order of the result is not important. So in the above example, [5, 3] is also correct.
  2. Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

题目地址:leetcode Single Number III

题意:给定一个数组,里面只有两个元素a,b出现一次,其他的元素均出现两次,求a,b

思路:

Once again, we need to use XOR to solve this problem. But this time, we need to do it in two passes:

  • In the first pass, we XOR all elements in the array, and get the XOR of the two numbers we need to find. Note that since the two numbers are distinct, so there must be a set bit (that is, the bit with value ‘1’) in the XOR result. Find out an arbitrary set bit (for example, the rightmost set bit).
  • In the second pass, we divide all numbers into two groups, one with the aforementioned bit set, another with the aforementinoed bit unset. Two different numbers we need to find must fall into thte two distrinct groups. XOR numbers in each group, we can find a number in either group.From https://discuss.leetcode.com/topic/21605/accepted-c-java-o-n-time-o-1-space-easy-solution-with-detail-explanations

就是首先先异或一次,这样就得到了a^b的值diff,接着由于a!=b,所以diff!=0,我们找diff最低位的元素作为分类的依据。(diff = diff&-diff 类似树状数组)因为,a和b这个位置的二进制不同,借此把a和b划分开。

接着,遍历数组,对于数组中的元素num, 若num & diff == 0 我们归为第一组,a ^= num 否则就是b^=num啦

C++

python

 

 

 

 

268. Missing Number

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

For example,
Given nums = [0, 1, 3] return 2.

Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

题目地址:leetcode Missing Number

题意:给定一个n个元素组成的数组,求0~n中缺失了哪一个?

思路:

看到这个,立马就觉得直接sum求和,也过了(其实数据量大会overflow)

Python

 

 

更好的方法是异或,利用两次异或 = 没有异或的性质 (如 x ^ 1 ^ 1 = x)

 

 

 

 

 

 

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode 位运算
本文地址:https://www.hrwhisper.me/leetcode-bit-manipulation/

打赏一杯咖啡钱呗

Leetcode , . permalink.

2 thoughts on “leetcode 位运算

  1. Single Number II不太懂Python版本的代码,为什么最后要转化成补码呢 计算机存负数不本来就是补码吗 为啥要我自己转

    • python 比较特殊,不止32位的整数表示。

      Negative numbers are written with a leading one instead of a leading zero. So if you are using only 8 bits for your twos-complement numbers, then you treat patterns from “00000000” to “01111111” as the whole numbers from 0 to 127, and reserve “1xxxxxxx” for writing negative numbers. A negative number, -x, is written using the bit pattern for (x-1) with all of the bits complemented (switched from 1 to 0 or 0 to 1). So -1 is complement(1 – 1) = complement(0) = “11111111”, and -10 is complement(10 – 1) = complement(9) = complement(“00001001”) = “11110110”. This means that negative numbers go all the way down to -128 (“10000000”).

      Of course, Python doesn’t use 8-bit numbers. It USED to use however many bits were native to your machine, but since that was non-portable, it has recently switched to using an INFINITE number of bits. Thus the number -5 is treated by bitwise operators as if it were written “…1111111111111111111011”.
      from https://wiki.python.org/moin/BitwiseOperators

Leave a Reply

Your email address will not be published. Required fields are marked *