切換
舊版
前往
大廳
主題

ZeroJudge - e351: And 運算 解題心得

Not In My Back Yard | 2019-08-15 23:34:06 | 巴幣 4 | 人氣 349

題目連結:


題目大意:
給定兩正整數 a 、 b (a 、 b < 2 ^ 64) ,求 a ~ b 之間(含 a 、 b )所有數字進行 and 之後的結果為何?



範例輸入:
12 15
2 3
8 13
17 23
11 15


範例輸出:
12
2
8
16
8


解題思維:
觀察以下例子(數字皆以二進位表示):
101101
000000
兩數之間的所有數字作 and 運算後結果為 000000

101101
100000
所有數字 and 的結果為 100000

101101
110000
數字們 and 後的結果為 100000

101101
101000
得結果為 101000

101101
101100
的結果為 101100

101101
111100
為 100000

101101
101101
是 101101

111111
100101
得 100000

由上面的例子我們可以看到,要從最左邊的位元開始往低位看。

兩者位元皆為 0 的位置略過;
當碰到兩者相同位置的位元皆為 1 時,則可知這個位元在從 a 數到 b 時皆不變,因此該位置的1 會在答案裡;
但是遇到其中一者為 1 ,另一者為 0 時,代表從 a 數到 b 此位元會變化,也就代表其後的位元皆會變化,因此從這個位元開始皆不需判斷。

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

Caritzoc
那個...程式碼好像放到c481的了...
然後不太懂說為什麼
101101
111100
and 會是100000 而不是101100?
2019-08-18 12:40:48
Not In My Back Yard
程式碼的網址已經修正,感謝提醒。

至於,and 的問題是因為省略了一些字詞。因為題目是給定兩正整數 a 、 b
試問 a ~ b 之間所有數字 and 起來的結果為何。因此本人直接略稱為「and 的結果」。

本人會對語句作一些修正,感謝提出問題。
2019-08-18 12:58:35
煌色鏡
請問這題測試執行可以AC,送出解答則WA(無輸出)
原因是出在哪裡呢?(不知道正式測資和測試執行時的側資差在哪邊)
還是我能否可以提供程式碼請大大幫忙檢查!!
2021-12-26 12:35:56
Not In My Back Yard
你當然可以提供程式碼。不然我沒辦法判斷XD
2021-12-26 12:58:11
煌色鏡
謝謝大大的幫忙,花了點時間研究,
讓我可以學到變量和純量的數字範圍和例外條件,
現在已經成功了!!
(不好意思讓大大看我寫的,雖然在寫信時已經有排好版了,但不知道傳過去還是會亂...)
2021-12-26 17:54:37

更多創作