给定数字从1到2 ^ 32-1，缺少一个。如何找到丢失的数量优化？ [英] Given numbers from 1 to 2^32-1, one is missing. How to find the missing number optimally?

问题描述

正在给2 ^ 32-2的范围从1到2 ^ 32-1的唯一号码。这是不可能适合所有的数字到内存中（这样的排序是不是一种选择）。你被要求寻找失踪的人数。什么是对这个问题最好的办法？

You are given 2^32-2 unique numbers that range from 1 to 2^32-1. It's impossible to fit all the numbers into memory (thus sorting is not an option). You are asked to find the missing number. What would be the best approach to this problem?

让我们假设你不能使用大整数，仅限于32位整数。

Let's assume you cannot use big-integers and are confined to 32bit ints.

INT ，则通过标准来传递。

ints are passed in through standard in.

推荐答案

主要编辑：的相信我做的事情更难比他们必须

Major Trust me to make things much harder than they have to be.

我在这里假设的数字是1至2 ³² - 1的包括的。这应该使用32位的1额外的存储空间。

I'm assuming here that the numbers are 1 to 2³² - 1 inclusive. This should use 1 extra memory location of 32 bits.

编辑：的，我想我可以逃脱魔术。不错啊。

I thought I could get away with magic. Ah well.

对于那些谁知道如何海明codeS的工作，这是同样的想法。

For those who know how Hamming Codes work, it's the same idea.

基本上，对于所有从0到2的数字 ^N - 1，恰好有2 ^{（正 - 1）功能} 1秒的数量的每个位的位置。因此异或所有这些数字实际上应该给予0。但是，由于一个数是缺少，该特定列将举一个，因为有中的一些在该比特位置为奇数。

Basically, for all numbers from 0 to 2ⁿ - 1, there are exactly 2^{(n - 1)} 1s in each bit position of the number. Therefore xoring all those numbers should actually give 0. However, since one number is missing, that particular column will give one, because there's an odd number of ones in that bit position.

注意：的虽然我个人preFER **操作的幂，我已经改变了雷^，因为这是在OP已经习惯了。不要混淆^为异。

Note: Although I personally prefer the ** operator for exponentiation, I've changed mine to ^ because that's what the OP has used. Don't confuse ^ for xor.

这篇关于给定数字从1到2 ^ 32-1，缺少一个。如何找到丢失的数量优化？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！