e351: And 運算

e351: And 運算

題目連結：e351: And 運算

題意：

給你兩個整數a,b(a,b<2^64)

求a到b之間所有整數(含)進行and運算的結果

解法：

首先題目沒說 a<=b (看到許多人都卡在這裡)，記得要交換

然後這題其實是HackerRank的題目：https://www.hackerrank.com/challenges/and-product/problem

因為那題測資太弱了，所以我就出了一個加強版的了

這題的O(1)的解法是這樣的：

首先，如果a和b之間有一個或一個以上的2的乘冪，答案一定是0

先舉例說明吧

如果a和b之間有一個2的乘冪

將a,b用二進位表示時

一定會長這個樣子：

a=0......(後面省略)

b=1......(後面省略)

假設a和b之間的2的乘冪為c

c一定會長這樣：

100000...(後面都是0)

所以這時c是一個位元遮罩(bit mask)

c後面的0會遮住後面所有的數字，全部都會變成0

而a前面的那個0也會在&的過程中把第一位也變成0

所以 a&......&c&......&b = a&b&c = 0

這題難是難在a和b之間沒有2的乘冪的時候

將a,b用二進位表示時

就會變成這個樣子這個樣子：

a=1......(後面省略)

b=1......(後面省略)

這時我們暫時把第一位省略

a和b有可能變成：

a=0......(後面省略)

b=1......(後面省略)

或是：

a=1......(後面省略)

b=1......(後面省略)

如果是第一種情況

那就會發現a和b之間出現了一個2的乘冪

這時就會回到上面那個狀況

這時再補上省略掉的第一位

因此答案就會是10000......(後面都是0)

如果是第二種情況

那就只要再繼續省略第二位、第三位，直到出現第一種情況就能算出答案了

這樣直接做的最差狀況是O(63)，也就是省略63位之後才算出解答

這樣已經可以過了，但是要怎麼做到O(1)呢？

這時我們可以利用Xor運算子

直接省略掉所有一樣的位數，讓它們全部都變成0

然後就只要做一次運算即可

Python:

time:0.4s

memory used:7.5MB

code:

1. from sys import stdin
2. while True:
3.  line=stdin.readline()
4.  if not line:
5.   break
6.  a,b=map(int,line.split())
7.  if a>b:
8.   a^=b
9.   b^=a
10.   a^=b
11.  s=bin(a^b)[2:]
12.  i=len(s)
13.  print((a>>(i-1))<<(i-1))

本人的分享到此結束
若有更好的想法或建議,請在留言區留言喔