algorithm - 仅使用比较运算符查找二进制数是否包含设置位（或连续设置位）

Question

我不确定这是否可能，但由于某种原因我不能放手。

我想知道如果一个数字存储在数据库中，我如何根据它是否设置了某个位来查询它。

示例：我存储的数字是 12 (1100)，我想查询数据库并查看是否有任何数字设置了第二位 (0100)。我不能在这里使用按位运算符。现在我想知道是否唯一的方法是查询二进制数的所有可能排列。

查询所有可能的排列是唯一的方法吗？

Answer 1

你应该做这样的事情 (x / 2^b) % 2 其中 b 是位数（从零开始）， / 是整数除法， % 是 mod 运算符， ^ 是幂运算符。不确定这将如何在 MongoDB 中表达，但它肯定会避免使用按位运算符。

db.whatever.find( { $where: "this.somefield / 4 % 2 == 1" } )

对于从位 b 开始的连续 n 个连续位，要检查的表达式为：

(x / 2^b) % (2^n) == 2^n - 1

Answer 2

由于 MongoDB 不包含按位运算符，因此没有有效的方法来执行此操作。它需要对每个文档进行全面扫描。虽然您可以使用 JavaScript 来执行findand$where 运算符，但它不会很快，特别是对于大型集合，我不会推荐它，除非是实验：

var num = 2;   // checking 3rd bit 
var bit = (Math.pow(2, num)).toString();
var query = "(this.bitValue & " + bit + ") > 0";
db.testCollection.find( { $where: query } )

您可以通过对数字进行过滤来进一步优化它：

db.testCollection.find({ bitValue: { $gte : bit }, $where: query } )

然后，您可以索引bitValue并仅查找大于或等于您正在检查的位的数字。这将阻止全表扫描。