用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找出概率

回答

相关问题