用XOR找出概率

假設x，y是兩個n比特的正整數。找出P（x + y = x^y）的概率，其中^表示XOR。我的老師給了我這個問題。他說答案是1/2 + 1/2^{n + 1}。但我找到了一些不同的答案。有人能幫我嗎？我的嘗試：對於n = 1，概率是3/4。現在假設我們已經找到了n位的概率。然後擴展到n + 1，我們在所有可能的3個案例中有2個有效案例。所以。概率變成（2/3）^ n * 3/4。但是這不起作用。有人可以幫我嗎？謝謝。用XOR找出概率

來源

2014-08-27 bstat isi

這個問題似乎是題外話題，因爲它是關於數學 – 2014-08-27 08:34:16

你如何處理'x + y'情況的溢出？對於'n = 1，x = 1，y = 1'，你可以說'x + y == x^y'或者'x + y！= x^y'，這取決於你如何處理溢出。 – 2014-08-27 08:37:36

這只是一個猜測，但如果他考慮基本概率爲3/4，那麼意味着'n = 1，x = 1，y = 1'意味着'x + y！= x^y'。否則，概率是1，對嗎？我在這裏糾正？ – shadow10 2014-08-27 12:02:30

老師給你的解決方案似乎是錯誤的。它應該是：

P = (3/4)^n

了嚴格的情況下，如果溢出不會被忽略，或

P = (3/4)^(n-1)

的鬆懈情況下，如果溢出被忽略。

我已經通過一個簡單的蠻力測試程序驗證了這一點，該程序僅評估給定n的所有可能輸入。

來源

2014-08-28 11:54:03

用XOR找出概率

回答

相關問題