アルゴリズム

【アルゴリズム脳トレ】leetcode easy 371 sum of two integer

投稿日：

こんにちは

今回の学びは

・pythonはintは桁の上限がない。floatはある。マイナスの表現は自分でやれ

・XORとANDで半加算器がつくれます

 

問題は。。。

（時間配分は5分問題理解　10分検討 10分実装  20分振り返り　の一文45分構成)

まずは入出力をしっかりおさえましょう。

 

この問題、難しくて解けませんでした。

+を使わずに考えてね、なんて

コンピューターの仕組みを理解した上で工夫したら解けるよね！？と挑発されているようです。

良問な気がします。

 

位置ビットづつ計算してcarry overを作ってという方法で

実装していまたのですが、

実装前後でこれは毎回書きましょう。timespace analysis (時間とスペースの分析）は　O(n)

これだとマイナスのケースがうまくいきません。

後半

a &= (2**33 - 1)

のようにすることで強制的に32bit Intにして

python3の上限がない制約を取っ払おうとしたのですが、それでも結果は変わらず

解答をみることとしました。

取りあえず11/13までクリアした私の誤解答はこちら

class Solution:
    def getSum(self, a: int, b: int) -> int:
        ans = 0
        carry = 0
        i = 0
        # turn them into 32 bit integer
        a &= (2**33 - 1)
        b &= (2**33 - 1)
        for k in range(32):
            a_ = a & 1
            b_ = b & 1
            if a_ == 1 and b_ == 1:
                if carry == 1:
                    x = 1
                else:
                    x = 0
                carry = 1
            elif a_ == 1 or b_ == 1:
                if carry == 1:
                    x = 0
                    carry = 1
                else:
                    x = 1
                    carry = 0
            else:
                if carry == 1:
                    x = 1
                    carry = 0
                else:
                    x = 0
                    carry = 0
            ans |= (x * 2**i)
            a >>= 1
            b >>= 1
            i += 1
        ans &= (2**33 - 1)
        return ans

 

# 1532pm start
(1, 2, 3),
(-2, 3, 1),
(3, 4, 7),
(8, 14, 22),
(-3, -9, -12),
# 2023pm
# やっぱりminusのケースでうまくいきません。。。
# むずかしですね。
# 11 / 13 test cases passed.

途中、家事やら早みまして時間の経過は大きいですが
これどうやって解くのでしょうか？

この時点で珍しくbad評価の方が多い問題であると気づきました。

どうやら皆さん解答がeasyとは思わないとの意見か、そもそも解答に納得いってないか。
自分がどう感じるか楽しみです。
ということで

discussion

みて見ていきましょう。
 

まずこちらの

解答

まじかーーーーー
XORとANDの組み合わせで足し算になってる〜〜〜〜〜〜〜〜〜〜〜
・足し算はXORとANDの組み合わせでできる

知らなかった
わからなかった


def _add(a, b):
    if b == 0:
        return a
    return _add(a ^ b, (a & b) << 1)

むむ

でもこれ

よく見てみたら、よくわからん。単順に一行とかじゃなくて再帰になってます

一行で (a ^ b) & ((a & b) << 1)でいけそうかと。。。思って喜んだのだが。

 

これも同じだね。でもキレイだね。

class Solution(object):
    def getSum(self, a, b):
        """
        :type a: int
        :type b: int
        :rtype: int
        """
        mask = 0xFFFF
        Max = 0x7FFF
        if b == 0:
            return ~(a ^ mask) if a >= Max else a
        return self.getSum((a ^ b) & mask, ((a & b & mask) <<1))

まだ理解できてないけど電子回路アダーーー！っ

ここいらで
pythonでのビット演算子を復習しよう

なぜならほぼ忘れているからだw
あら〜2の補数だなんて懐かしい、みたいな気持ちに浸りつつ復習しよう
すると

x = 1
を反転させて
x = ~x
x = x + 1
をすれば-1となることがわかる
これが2の補数だ

わかりやすく表示すると
print(bin(1&0xff))
0b1

print(bin(~1&0xff))
0b11111110

print(bin((~1+1)&0xff))
0b11111111

のような感じです


そして
それから電子回路勉強してみよう
この電子回路の解答には様々なコンピューターの真実が隠されていそうな気がするからだ。
en.wiki digital adder
おうおう日本語でもありますなぁ。

wikiだけでは理解できませんでしたので動画youtube電卓で足し算ができる仕組なんかも見させていただきました。

半加算器では1たす1ができます。それ以外はできません！きっぱり。

 

 

なんどやっても、マイナスの計算がうまくいきません。

一つは、half adderとfull adderの実装が微妙にまちがっていた。

最初はfull_adderをXORつかわないパターンでかいていたのですが、微妙にバグをおいているようで

シンプルなXORとANDをつかった半加算器に切り替えました。それはよかったです。

それでfull加算器もつくりました。

このあたりの文字列をつかった加算器の実装は参考にしました。でも疑問、なぜ文字列やねん！と。最終的には私のかいた

intで扱っている加算器の方が良いでしょう。:)

 

２つめは、マイナスの計算、特に-3, -9が答え-12になってほしいのに　4294967284　となるやん！

なんじゃこら

最終的な糸口は

これって答え的には合ってんじゃね！？と

print(bin(ans & 0xff))

をついかしてみると

0b11110100

だと

おっしゃるわけです。

ふとipythonをおこして、これって-12のことなんじゃね！？と確かめると

In [42]: x
Out[42]: -12

In [43]: bin(x)
Out[43]: '-0b1100'

In [44]: bin(x & 0xff)
Out[44]: '0b11110100'

そうだ。といことになって、自分の計算にやっと自信がもてました。

あとは、若干こじつけだけど

こんなデバッグで-12のパターンをとおしました。

このアイデアはこちらの記事（ビット表現からサインed イントへの変換方法）も参考にしました。

if byte > 127:
    return (256-byte) * (-1)
else:
    return byte

・pythonはintは桁の上限がない。floatはある。マイナスの表現は自分でやれ

という学びを得ました

def getSum(self, a: int, b: int) -> int:
        i = 0
        ans = 0
        c = 0 # initally C is 0
        for i in range(32):
            a_ = (a >> i) & 1
            b_ = (b >> i) & 1
            s, c = self.full_adder(a_, b_, c)
            ans = ans | (s << i)
        print(bin(ans & 0xff))
        if ans > 0xff:
            print("dekai")
            ans = (0xff - (ans & 0xff) + 1) * -1
        else:
            print("chisai")
        return ans

後は、これを少しばかりMAX = 0xffffと汎用化させて無事クリアとなりました！

 

最終的な実装です

マイナスの扱いがすごくむずかしかったです。

from typing import Tuple
class Solution:
    def half_adder(self, a, b) -> Tuple[int, int]:
        s = 1 & (a ^ b)
        c = 1 & (a & b)
        return (s, c)

    def full_adder(self, a, b, x) -> Tuple[int, int]:
        (s1, c1) = self.half_adder(a, b)
        (s, c2) = self.half_adder(s1, x)
        c = (c1 | c2)
        return (s, c)


    def getSum(self, a: int, b: int) -> int:
        # a = (a & 2**33-1)
        # b = (b & 2**33-1)
        i = 0
        ans = 0
        c = 0 # initally C is 0
        for i in range(32):
            a_ = (a >> i) & 1
            b_ = (b >> i) & 1
            s, c = self.full_adder(a_, b_, c)
            ans = ans | (s << i)
        #print(bin(ans & 0xff))
        MAX = 0xffff
        if ans > MAX:
            ans = (MAX - (ans & MAX) + 1) * -1
        return ans

 



実装後です。timespace analysis (時間とスペースの分析）は　O(N)


 


 


まとめ


・pythonはintは桁の上限がない。floatはある。マイナスの表現は自分でやれ


・XORとANDで半加算器がつくれます


 


 


最後に一言、これはeasyな問題ではないです。に一票！


勉強なりました！


以上です

							

						


												
					

				
							        
	
									

						
							        
	
					

							

		
        
	

						
					


												
	

	

	
 

													
						

							-アルゴリズム

													


					

				

				
			

		

	

	
	

	


















Copyright© CTOを目指す日記 ,  2024 All Rights Reserved.