SERVER-3518 Bit test query operators

7 files changed, 1345 insertions, 2 deletions

diff --git a/src/mongo/db/matcher/expression.h b/src/mongo/db/matcher/expression.h
index bc2a0410839..52f026d589e 100644
--- a/src/mongo/db/matcher/expression.h
+++ b/src/mongo/db/matcher/expression.h
@@ -67,6 +67,10 @@ public:
         MOD,
         EXISTS,
         MATCH_IN,
+        BITS_ALL_SET,
+        BITS_ALL_CLEAR,
+        BITS_ANY_SET,
+        BITS_ANY_CLEAR,
 
         // Negations.
         NOT,
diff --git a/src/mongo/db/matcher/expression_leaf.cpp b/src/mongo/db/matcher/expression_leaf.cpp
index f826b95ecb3..208f2f67630 100644
--- a/src/mongo/db/matcher/expression_leaf.cpp
+++ b/src/mongo/db/matcher/expression_leaf.cpp
@@ -661,4 +661,228 @@ void InMatchExpression::copyTo(InMatchExpression* toFillIn) const {
     toFillIn->init(path());
     _arrayEntries.copyTo(toFillIn->_arrayEntries);
 }
+
+// -----------
+
+const double BitTestMatchExpression::kLongLongMaxPlusOneAsDouble =
+    scalbn(1, std::numeric_limits<long long>::digits);
+
+Status BitTestMatchExpression::init(StringData path, std::vector<uint32_t> bitPositions) {
+    _bitPositions = std::move(bitPositions);
+    return initPath(path);
+}
+
+Status BitTestMatchExpression::init(StringData path, uint64_t bitMask) {
+    for (int bit = 0; bit < 64; bit++) {
+        if (bitMask & (1LL << bit)) {
+            _bitPositions.push_back(bit);
+        }
+    }
+
+    return initPath(path);
+}
+
+Status BitTestMatchExpression::init(StringData path,
+                                    const char* bitMaskBinary,
+                                    uint32_t bitMaskLen) {
+    for (uint32_t byte = 0; byte < bitMaskLen; byte++) {
+        char byteAt = bitMaskBinary[byte];
+        if (!byteAt) {
+            continue;
+        }
+
+        for (int bit = 0; bit < 8; bit++) {
+            if (byteAt & (1 << bit)) {
+                _bitPositions.push_back(8 * byte + bit);
+            }
+        }
+    }
+
+    return initPath(path);
+}
+
+bool BitTestMatchExpression::needFurtherBitTests(bool isBitSet) const {
+    const MatchType mt = matchType();
+
+    return (isBitSet && (mt == BITS_ALL_SET || mt == BITS_ANY_CLEAR)) ||
+        (!isBitSet && (mt == BITS_ALL_CLEAR || mt == BITS_ANY_SET));
+}
+
+bool BitTestMatchExpression::performBitTest(long long eValue) const {
+    const MatchType mt = matchType();
+
+    // Test each bit position.
+    for (auto bitPosition : _bitPositions) {
+        bool isBitSet;
+        if (bitPosition >= 63) {
+            // If position to test is longer than 64 bits, sign-extend.
+            isBitSet = eValue < 0;
+        } else {
+            isBitSet = eValue & (1LL << bitPosition);
+        }
+
+        if (!needFurtherBitTests(isBitSet)) {
+            // If we can skip the rest of the tests, that means we succeeded with _ANY_ or failed
+            // with _ALL_.
+            return mt == BITS_ANY_SET || mt == BITS_ANY_CLEAR;
+        }
+    }
+
+    // If we finished all the tests, that means we succeeded with _ALL_ or failed with _ANY_.
+    return mt == BITS_ALL_SET || mt == BITS_ALL_CLEAR;
+}
+
+bool BitTestMatchExpression::performBitTest(const char* eBinary, uint32_t eBinaryLen) const {
+    const MatchType mt = matchType();
+
+    // Test each bit position.
+    for (auto bitPosition : _bitPositions) {
+        bool isBitSet;
+        if (bitPosition >= eBinaryLen * 8) {
+            // If position to test is longer than the data to test against, zero-extend.
+            isBitSet = false;
+        } else {
+            // Map to byte position and bit position within that byte. Note that byte positions
+            // start at position 0 in the char array, and bit positions start at the least
+            // significant bit.
+            int bytePosition = bitPosition / 8;
+            int bit = bitPosition % 8;
+            char byte = eBinary[bytePosition];
+
+            isBitSet = byte & (1 << bit);
+        }
+
+        if (!needFurtherBitTests(isBitSet)) {
+            // If we can skip the rest fo the tests, that means we succeeded with _ANY_ or failed
+            // with _ALL_.
+            return mt == BITS_ANY_SET || mt == BITS_ANY_CLEAR;
+        }
+    }
+
+    // If we finished all the tests, that means we succeeded with _ALL_ or failed with _ANY_.
+    return mt == BITS_ALL_SET || mt == BITS_ALL_CLEAR;
+}
+
+bool BitTestMatchExpression::matchesSingleElement(const BSONElement& e) const {
+    // Validate 'e' is a number or a BinData.
+    if (!e.isNumber() && e.type() != BSONType::BinData) {
+        return false;
+    }
+
+    if (e.type() == BSONType::BinData) {
+        int eBinaryLen;  // Length of eBinary (in bytes).
+        const char* eBinary = e.binData(eBinaryLen);
+        return performBitTest(eBinary, eBinaryLen);
+    }
+
+    invariant(e.isNumber());
+
+    if (e.type() == BSONType::NumberDouble) {
+        double eDouble = e.numberDouble();
+
+        // NaN doubles are rejected.
+        if (std::isnan(eDouble)) {
+            return false;
+        }
+
+        // Integral doubles that are too large or small to be represented as a 64-bit signed
+        // integer are treated as 0. We use 'kLongLongMaxAsDouble' because if we just did
+        // eDouble > 2^63-1, it would be compared against 2^63. eDouble=2^63 would not get caught
+        // that way.
+        if (eDouble >= kLongLongMaxPlusOneAsDouble ||
+            eDouble < std::numeric_limits<long long>::min()) {
+            return false;
+        }
+
+        // This checks if e is an integral double.
+        if (eDouble != static_cast<double>(static_cast<long long>(eDouble))) {
+            return false;
+        }
+    }
+
+    long long eValue = e.numberLong();
+    return performBitTest(eValue);
+}
+
+void BitTestMatchExpression::debugString(StringBuilder& debug, int level) const {
+    _debugAddSpace(debug, level);
+
+    debug << path() << " ";
+
+    switch (matchType()) {
+        case BITS_ALL_SET:
+            debug << "$bitsAllSet:";
+            break;
+        case BITS_ALL_CLEAR:
+            debug << "$bitsAllClear:";
+            break;
+        case BITS_ANY_SET:
+            debug << "$bitsAnySet:";
+            break;
+        case BITS_ANY_CLEAR:
+            debug << "$bitsAnyClear:";
+            break;
+        default:
+            invariant(false);
+    }
+
+    debug << " [";
+    for (size_t i = 0; i < _bitPositions.size(); i++) {
+        debug << _bitPositions[i];
+        if (i != _bitPositions.size() - 1) {
+            debug << ", ";
+        }
+    }
+    debug << "]";
+
+    MatchExpression::TagData* td = getTag();
+    if (td) {
+        debug << " ";
+        td->debugString(&debug);
+    }
+}
+
+void BitTestMatchExpression::toBSON(BSONObjBuilder* out) const {
+    string opString = "";
+
+    switch (matchType()) {
+        case BITS_ALL_SET:
+            opString = "$bitsAllSet";
+            break;
+        case BITS_ALL_CLEAR:
+            opString = "$bitsAllClear";
+            break;
+        case BITS_ANY_SET:
+            opString = "$bitsAnySet";
+            break;
+        case BITS_ANY_CLEAR:
+            opString = "$bitsAnyClear";
+            break;
+        default:
+            invariant(false);
+    }
+
+    BSONArrayBuilder arrBob;
+    for (auto bitPosition : _bitPositions) {
+        arrBob.append(bitPosition);
+    }
+    arrBob.doneFast();
+
+    out->append(path(), BSON(opString << arrBob.arr()));
+}
+
+bool BitTestMatchExpression::equivalent(const MatchExpression* other) const {
+    if (matchType() != other->matchType()) {
+        return false;
+    }
+
+    const BitTestMatchExpression* realOther = static_cast<const BitTestMatchExpression*>(other);
+
+    std::vector<uint32_t> myBitPositions = getBitPositions();
+    std::vector<uint32_t> otherBitPositions = realOther->getBitPositions();
+    std::sort(myBitPositions.begin(), myBitPositions.end());
+    std::sort(otherBitPositions.begin(), otherBitPositions.end());
+
+    return path() == realOther->path() && myBitPositions == otherBitPositions;
+}
 }
diff --git a/src/mongo/db/matcher/expression_leaf.h b/src/mongo/db/matcher/expression_leaf.h
index 5de55766b44..4ccb2f01102 100644
--- a/src/mongo/db/matcher/expression_leaf.h
+++ b/src/mongo/db/matcher/expression_leaf.h
@@ -455,4 +455,121 @@ private:
     BSONType _type;
 };
 
+/**
+ * Bit test query operators include $bitsAllSet, $bitsAllClear, $bitsAnySet, and $bitsAnyClear.
+ */
+class BitTestMatchExpression : public LeafMatchExpression {
+public:
+    // Constant used in matchesSingleElement() and MatchExpressionParser::_parseBitTest. Is a
+    // double representation of 2^63.
+    static const double kLongLongMaxPlusOneAsDouble;
+
+    BitTestMatchExpression(MatchType type) : LeafMatchExpression(type) {}
+    virtual ~BitTestMatchExpression() {}
+
+    /**
+     * Initialize with either bit positions, a 64-bit numeric bitmask, or a char array
+     * bitmask.
+     */
+    Status init(StringData path, std::vector<uint32_t> bitPositions);
+    Status init(StringData path, uint64_t bitMask);
+    Status init(StringData path, const char* bitMaskBinary, uint32_t bitMaskLen);
+
+    virtual bool matchesSingleElement(const BSONElement& e) const;
+
+    virtual void debugString(StringBuilder& debug, int level) const;
+
+    virtual void toBSON(BSONObjBuilder* out) const;
+
+    virtual bool equivalent(const MatchExpression* other) const;
+
+    size_t numBitPositions() const {
+        return _bitPositions.size();
+    }
+
+    const std::vector<uint32_t>& getBitPositions() const {
+        return _bitPositions;
+    }
+
+protected:
+    /**
+     * Used to copy this match expression to another BitTestMatchExpression. Does not take
+     * ownership.
+     */
+    void initClone(BitTestMatchExpression* clone) const {
+        clone->init(path(), _bitPositions);
+        if (getTag()) {
+            clone->setTag(getTag()->clone());
+        }
+    }
+
+private:
+    /**
+     * Performs bit test using bit positions on 'eValue' and returns whether or not the bit test
+     * passes.
+     */
+    bool performBitTest(long long eValue) const;
+
+    /**
+     * Performs bit test using bit positions on 'eBinary' with length (in bytes) 'eBinaryLen' and
+     * returns whether or not the bit test passes.
+     */
+    bool performBitTest(const char* eBinary, uint32_t eBinaryLen) const;
+
+    /**
+     * Helper function for performBitTest(...).
+     *
+     * needFurtherBitTests() determines if the result of a bit-test ('isBitSet') is enough
+     * information to skip the rest of the bit tests.
+     **/
+    bool needFurtherBitTests(bool isBitSet) const;
+
+    // Vector of bit positions to test, with bit position 0 being the least significant bit.
+    std::vector<uint32_t> _bitPositions;
+};
+
+class BitsAllSetMatchExpression : public BitTestMatchExpression {
+public:
+    BitsAllSetMatchExpression() : BitTestMatchExpression(BITS_ALL_SET) {}
+    virtual std::unique_ptr<MatchExpression> shallowClone() const {
+        std::unique_ptr<BitTestMatchExpression> bitTestMatchExpression =
+            stdx::make_unique<BitsAllSetMatchExpression>();
+        initClone(bitTestMatchExpression.get());
+        return std::move(bitTestMatchExpression);
+    }
+};
+
+class BitsAllClearMatchExpression : public BitTestMatchExpression {
+public:
+    BitsAllClearMatchExpression() : BitTestMatchExpression(BITS_ALL_CLEAR) {}
+    virtual std::unique_ptr<MatchExpression> shallowClone() const {
+        std::unique_ptr<BitTestMatchExpression> bitTestMatchExpression =
+            stdx::make_unique<BitsAllClearMatchExpression>();
+        initClone(bitTestMatchExpression.get());
+        return std::move(bitTestMatchExpression);
+    }
+};
+
+class BitsAnySetMatchExpression : public BitTestMatchExpression {
+public:
+    BitsAnySetMatchExpression() : BitTestMatchExpression(BITS_ANY_SET) {}
+    virtual std::unique_ptr<MatchExpression> shallowClone() const {
+        std::unique_ptr<BitTestMatchExpression> bitTestMatchExpression =
+            stdx::make_unique<BitsAnySetMatchExpression>();
+        initClone(bitTestMatchExpression.get());
+        return std::move(bitTestMatchExpression);
+    }
+};
+
+class BitsAnyClearMatchExpression : public BitTestMatchExpression {
+public:
+    BitsAnyClearMatchExpression() : BitTestMatchExpression(BITS_ANY_CLEAR) {}
+    virtual std::unique_ptr<MatchExpression> shallowClone() const {
+        std::unique_ptr<BitTestMatchExpression> bitTestMatchExpression =
+            stdx::make_unique<BitsAnyClearMatchExpression>();
+        initClone(bitTestMatchExpression.get());
+        return std::move(bitTestMatchExpression);
+    }
+};
+
 }  // namespace mongo
diff --git a/src/mongo/db/matcher/expression_leaf_test.cpp b/src/mongo/db/matcher/expression_leaf_test.cpp
index ff3f65efb34..efe64befcd3 100644
--- a/src/mongo/db/matcher/expression_leaf_test.cpp
+++ b/src/mongo/db/matcher/expression_leaf_test.cpp
@@ -1716,4 +1716,558 @@ TEST( InMatchExpression, MatchesIndexKeyArrayValue ) {
                                       "" << BSON_ARRAY( 8 << "ac" ) ), indexSpec ) );
 }
 */
+
+std::vector<uint32_t> bsonArrayToBitPositions(const BSONArray& ba) {
+    std::vector<uint32_t> bitPositions;
+
+    // Convert BSONArray of bit positions to int vector
+    for (const auto& elt : ba) {
+        bitPositions.push_back(elt._numberInt());
+    }
+
+    return bitPositions;
+}
+
+TEST(BitTestMatchExpression, DoesNotMatchOther) {
+    std::vector<uint32_t> bitPositions;
+
+    BSONObj notMatch1 = fromjson("{a: {}}");     // Object
+    BSONObj notMatch2 = fromjson("{a: null}");   // Null
+    BSONObj notMatch3 = fromjson("{a: []}");     // Array
+    BSONObj notMatch4 = fromjson("{a: true}");   // Boolean
+    BSONObj notMatch5 = fromjson("{a: ''}");     // String
+    BSONObj notMatch6 = fromjson("{a: 5.5}");    // Non-integral Double
+    BSONObj notMatch7 = fromjson("{a: NaN}");    // NaN
+    BSONObj notMatch8 = fromjson("{a: 1e100}");  // Too-Large Double
+    BSONObj notMatch9 = fromjson("{a: ObjectId('000000000000000000000000')}");  // OID
+    BSONObj notMatch10 = fromjson("{a: Date(54)}");                             // Date
+
+    BitsAllSetMatchExpression balls;
+    BitsAllClearMatchExpression ballc;
+    BitsAnySetMatchExpression banys;
+    BitsAnyClearMatchExpression banyc;
+
+    ASSERT_OK(balls.init("a", bitPositions));
+    ASSERT_OK(ballc.init("a", bitPositions));
+    ASSERT_OK(banys.init("a", bitPositions));
+    ASSERT_OK(banyc.init("a", bitPositions));
+    ASSERT_EQ((size_t)0, balls.numBitPositions());
+    ASSERT_EQ((size_t)0, ballc.numBitPositions());
+    ASSERT_EQ((size_t)0, banys.numBitPositions());
+    ASSERT_EQ((size_t)0, banyc.numBitPositions());
+    ASSERT(!balls.matchesSingleElement(notMatch1["a"]));
+    ASSERT(!balls.matchesSingleElement(notMatch2["a"]));
+    ASSERT(!balls.matchesSingleElement(notMatch3["a"]));
+    ASSERT(!balls.matchesSingleElement(notMatch4["a"]));
+    ASSERT(!balls.matchesSingleElement(notMatch5["a"]));
+    ASSERT(!balls.matchesSingleElement(notMatch6["a"]));
+    ASSERT(!balls.matchesSingleElement(notMatch7["a"]));
+    ASSERT(!balls.matchesSingleElement(notMatch8["a"]));
+    ASSERT(!balls.matchesSingleElement(notMatch9["a"]));
+    ASSERT(!balls.matchesSingleElement(notMatch10["a"]));
+    ASSERT(!ballc.matchesSingleElement(notMatch1["a"]));
+    ASSERT(!ballc.matchesSingleElement(notMatch2["a"]));
+    ASSERT(!ballc.matchesSingleElement(notMatch3["a"]));
+    ASSERT(!ballc.matchesSingleElement(notMatch4["a"]));
+    ASSERT(!ballc.matchesSingleElement(notMatch5["a"]));
+    ASSERT(!ballc.matchesSingleElement(notMatch6["a"]));
+    ASSERT(!ballc.matchesSingleElement(notMatch7["a"]));
+    ASSERT(!ballc.matchesSingleElement(notMatch8["a"]));
+    ASSERT(!ballc.matchesSingleElement(notMatch9["a"]));
+    ASSERT(!ballc.matchesSingleElement(notMatch10["a"]));
+    ASSERT(!banys.matchesSingleElement(notMatch1["a"]));
+    ASSERT(!banys.matchesSingleElement(notMatch2["a"]));
+    ASSERT(!banys.matchesSingleElement(notMatch3["a"]));
+    ASSERT(!banys.matchesSingleElement(notMatch4["a"]));
+    ASSERT(!banys.matchesSingleElement(notMatch5["a"]));
+    ASSERT(!banys.matchesSingleElement(notMatch6["a"]));
+    ASSERT(!banys.matchesSingleElement(notMatch7["a"]));
+    ASSERT(!banys.matchesSingleElement(notMatch8["a"]));
+    ASSERT(!banys.matchesSingleElement(notMatch9["a"]));
+    ASSERT(!banys.matchesSingleElement(notMatch10["a"]));
+    ASSERT(!banyc.matchesSingleElement(notMatch1["a"]));
+    ASSERT(!banyc.matchesSingleElement(notMatch2["a"]));
+    ASSERT(!banyc.matchesSingleElement(notMatch3["a"]));
+    ASSERT(!banyc.matchesSingleElement(notMatch4["a"]));
+    ASSERT(!banyc.matchesSingleElement(notMatch5["a"]));
+    ASSERT(!banyc.matchesSingleElement(notMatch6["a"]));
+    ASSERT(!banyc.matchesSingleElement(notMatch7["a"]));
+    ASSERT(!banyc.matchesSingleElement(notMatch8["a"]));
+    ASSERT(!banyc.matchesSingleElement(notMatch9["a"]));
+    ASSERT(!banyc.matchesSingleElement(notMatch10["a"]));
+}
+
+TEST(BitTestMatchExpression, MatchBinaryWithLongBitMask) {
+    long long bitMask = 54;
+
+    BSONObj match = fromjson("{a: {$binary: 'NgAAAAAAAAAAAAAAAAAAAAAAAAAA', $type: '00'}}");
+
+    BitsAllSetMatchExpression balls;
+    BitsAllClearMatchExpression ballc;
+    BitsAnySetMatchExpression banys;
+    BitsAnyClearMatchExpression banyc;
+
+    ASSERT_OK(balls.init("a", bitMask));
+    ASSERT_OK(ballc.init("a", bitMask));
+    ASSERT_OK(banys.init("a", bitMask));
+    ASSERT_OK(banyc.init("a", bitMask));
+    std::vector<uint32_t> bitPositions = balls.getBitPositions();
+    ASSERT(balls.matchesSingleElement(match["a"]));
+    ASSERT(!ballc.matchesSingleElement(match["a"]));
+    ASSERT(banys.matchesSingleElement(match["a"]));
+    ASSERT(!banyc.matchesSingleElement(match["a"]));
+}
+
+TEST(BitTestMatchExpression, MatchLongWithBinaryBitMask) {
+    const char* bitMask = "\x36\x00\x00\x00";
+
+    BSONObj match = fromjson("{a: 54}");
+
+    BitsAllSetMatchExpression balls;
+    BitsAllClearMatchExpression ballc;
+    BitsAnySetMatchExpression banys;
+    BitsAnyClearMatchExpression banyc;
+
+    ASSERT_OK(balls.init("a", bitMask, 4));
+    ASSERT_OK(ballc.init("a", bitMask, 4));
+    ASSERT_OK(banys.init("a", bitMask, 4));
+    ASSERT_OK(banyc.init("a", bitMask, 4));
+    ASSERT(balls.matchesSingleElement(match["a"]));
+    ASSERT(!ballc.matchesSingleElement(match["a"]));
+    ASSERT(banys.matchesSingleElement(match["a"]));
+    ASSERT(!banyc.matchesSingleElement(match["a"]));
+}
+
+TEST(BitTestMatchExpression, MatchesEmpty) {
+    std::vector<uint32_t> bitPositions;
+
+    BSONObj match1 = fromjson("{a: NumberInt(54)}");
+    BSONObj match2 = fromjson("{a: NumberLong(54)}");
+    BSONObj match3 = fromjson("{a: 54.0}");
+    BSONObj match4 = fromjson("{a: {$binary: '2AAAAAAAAAAAAAAAAAAAAAAAAAAA', $type: '00'}}");
+
+    BitsAllSetMatchExpression balls;
+    BitsAllClearMatchExpression ballc;
+    BitsAnySetMatchExpression banys;
+    BitsAnyClearMatchExpression banyc;
+
+    ASSERT_OK(balls.init("a", bitPositions));
+    ASSERT_OK(ballc.init("a", bitPositions));
+    ASSERT_OK(banys.init("a", bitPositions));
+    ASSERT_OK(banyc.init("a", bitPositions));
+    ASSERT_EQ((size_t)0, balls.numBitPositions());
+    ASSERT_EQ((size_t)0, ballc.numBitPositions());
+    ASSERT_EQ((size_t)0, banys.numBitPositions());
+    ASSERT_EQ((size_t)0, banyc.numBitPositions());
+    ASSERT(balls.matchesSingleElement(match1["a"]));
+    ASSERT(balls.matchesSingleElement(match2["a"]));
+    ASSERT(balls.matchesSingleElement(match3["a"]));
+    ASSERT(balls.matchesSingleElement(match4["a"]));
+    ASSERT(ballc.matchesSingleElement(match1["a"]));
+    ASSERT(ballc.matchesSingleElement(match2["a"]));
+    ASSERT(ballc.matchesSingleElement(match3["a"]));
+    ASSERT(ballc.matchesSingleElement(match4["a"]));
+    ASSERT(!banys.matchesSingleElement(match1["a"]));
+    ASSERT(!banys.matchesSingleElement(match2["a"]));
+    ASSERT(!banys.matchesSingleElement(match3["a"]));
+    ASSERT(!banys.matchesSingleElement(match4["a"]));
+    ASSERT(!banyc.matchesSingleElement(match1["a"]));
+    ASSERT(!banyc.matchesSingleElement(match2["a"]));
+    ASSERT(!banyc.matchesSingleElement(match3["a"]));
+    ASSERT(!banyc.matchesSingleElement(match4["a"]));
+}
+
+TEST(BitTestMatchExpression, MatchesInteger) {
+    BSONArray bas = BSON_ARRAY(1 << 2 << 4 << 5);
+    BSONArray bac = BSON_ARRAY(0 << 3 << 600);
+    std::vector<uint32_t> bitPositionsSet = bsonArrayToBitPositions(bas);
+    std::vector<uint32_t> bitPositionsClear = bsonArrayToBitPositions(bac);
+
+    BSONObj match1 = fromjson("{a: NumberInt(54)}");
+    BSONObj match2 = fromjson("{a: NumberLong(54)}");
+    BSONObj match3 = fromjson("{a: 54.0}");
+
+    BitsAllSetMatchExpression balls;
+    BitsAllClearMatchExpression ballc;
+    BitsAnySetMatchExpression banys;
+    BitsAnyClearMatchExpression banyc;
+
+    ASSERT_OK(balls.init("a", bitPositionsSet));
+    ASSERT_OK(ballc.init("a", bitPositionsClear));
+    ASSERT_OK(banys.init("a", bitPositionsSet));
+    ASSERT_OK(banyc.init("a", bitPositionsClear));
+    ASSERT_EQ((size_t)4, balls.numBitPositions());
+    ASSERT_EQ((size_t)3, ballc.numBitPositions());
+    ASSERT_EQ((size_t)4, banys.numBitPositions());
+    ASSERT_EQ((size_t)3, banyc.numBitPositions());
+    ASSERT(balls.matchesSingleElement(match1["a"]));
+    ASSERT(balls.matchesSingleElement(match2["a"]));
+    ASSERT(balls.matchesSingleElement(match3["a"]));
+    ASSERT(ballc.matchesSingleElement(match1["a"]));
+    ASSERT(ballc.matchesSingleElement(match2["a"]));
+    ASSERT(ballc.matchesSingleElement(match3["a"]));
+    ASSERT(banys.matchesSingleElement(match1["a"]));
+    ASSERT(banys.matchesSingleElement(match2["a"]));
+    ASSERT(banys.matchesSingleElement(match3["a"]));
+    ASSERT(banyc.matchesSingleElement(match1["a"]));
+    ASSERT(banyc.matchesSingleElement(match2["a"]));
+    ASSERT(banyc.matchesSingleElement(match3["a"]));
+}
+
+TEST(BitTestMatchExpression, MatchesNegativeInteger) {
+    BSONArray bas = BSON_ARRAY(1 << 3 << 6 << 7 << 33);
+    BSONArray bac = BSON_ARRAY(0 << 2 << 4 << 5);
+    std::vector<uint32_t> bitPositionsSet = bsonArrayToBitPositions(bas);
+    std::vector<uint32_t> bitPositionsClear = bsonArrayToBitPositions(bac);
+
+    BSONObj match1 = fromjson("{a: NumberInt(-54)}");
+    BSONObj match2 = fromjson("{a: NumberLong(-54)}");
+    BSONObj match3 = fromjson("{a: -54.0}");
+
+    BitsAllSetMatchExpression balls;
+    BitsAllClearMatchExpression ballc;
+    BitsAnySetMatchExpression banys;
+    BitsAnyClearMatchExpression banyc;
+
+    ASSERT_OK(balls.init("a", bitPositionsSet));
+    ASSERT_OK(ballc.init("a", bitPositionsClear));
+    ASSERT_OK(banys.init("a", bitPositionsSet));
+    ASSERT_OK(banyc.init("a", bitPositionsClear));
+    ASSERT_EQ((size_t)5, balls.numBitPositions());
+    ASSERT_EQ((size_t)4, ballc.numBitPositions());
+    ASSERT_EQ((size_t)5, banys.numBitPositions());
+    ASSERT_EQ((size_t)4, banyc.numBitPositions());
+    ASSERT(balls.matchesSingleElement(match1["a"]));
+    ASSERT(balls.matchesSingleElement(match2["a"]));
+    ASSERT(balls.matchesSingleElement(match3["a"]));
+    ASSERT(ballc.matchesSingleElement(match1["a"]));
+    ASSERT(ballc.matchesSingleElement(match2["a"]));
+    ASSERT(ballc.matchesSingleElement(match3["a"]));
+    ASSERT(banys.matchesSingleElement(match1["a"]));
+    ASSERT(banys.matchesSingleElement(match2["a"]));
+    ASSERT(banys.matchesSingleElement(match3["a"]));
+    ASSERT(banyc.matchesSingleElement(match1["a"]));
+    ASSERT(banyc.matchesSingleElement(match2["a"]));
+    ASSERT(banyc.matchesSingleElement(match3["a"]));
+}
+
+TEST(BitTestMatchExpression, MatchesIntegerWithBitMask) {
+    long long bitMaskSet = 54;
+    long long bitMaskClear = 201;
+
+    BSONObj match1 = fromjson("{a: NumberInt(54)}");
+    BSONObj match2 = fromjson("{a: NumberLong(54)}");
+    BSONObj match3 = fromjson("{a: 54.0}");
+
+    BitsAllSetMatchExpression balls;
+    BitsAllClearMatchExpression ballc;
+    BitsAnySetMatchExpression banys;
+    BitsAnyClearMatchExpression banyc;
+
+    ASSERT_OK(balls.init("a", bitMaskSet));
+    ASSERT_OK(ballc.init("a", bitMaskClear));
+    ASSERT_OK(banys.init("a", bitMaskSet));
+    ASSERT_OK(banyc.init("a", bitMaskClear));
+    ASSERT(balls.matchesSingleElement(match1["a"]));
+    ASSERT(balls.matchesSingleElement(match2["a"]));
+    ASSERT(balls.matchesSingleElement(match3["a"]));
+    ASSERT(ballc.matchesSingleElement(match1["a"]));
+    ASSERT(ballc.matchesSingleElement(match2["a"]));
+    ASSERT(ballc.matchesSingleElement(match3["a"]));
+    ASSERT(banys.matchesSingleElement(match1["a"]));
+    ASSERT(banys.matchesSingleElement(match2["a"]));
+    ASSERT(banys.matchesSingleElement(match3["a"]));
+    ASSERT(banyc.matchesSingleElement(match1["a"]));
+    ASSERT(banyc.matchesSingleElement(match2["a"]));
+    ASSERT(banyc.matchesSingleElement(match3["a"]));
+}
+
+TEST(BitTestMatchExpression, MatchesNegativeIntegerWithBitMask) {
+    long long bitMaskSet = 10;
+    long long bitMaskClear = 5;
+
+    BSONObj match1 = fromjson("{a: NumberInt(-54)}");
+    BSONObj match2 = fromjson("{a: NumberLong(-54)}");
+    BSONObj match3 = fromjson("{a: -54.0}");
+
+    BitsAllSetMatchExpression balls;
+    BitsAllClearMatchExpression ballc;
+    BitsAnySetMatchExpression banys;
+    BitsAnyClearMatchExpression banyc;
+
+    ASSERT_OK(balls.init("a", bitMaskSet));
+    ASSERT_OK(ballc.init("a", bitMaskClear));
+    ASSERT_OK(banys.init("a", bitMaskSet));
+    ASSERT_OK(banyc.init("a", bitMaskClear));
+    ASSERT(balls.matchesSingleElement(match1["a"]));
+    ASSERT(balls.matchesSingleElement(match2["a"]));
+    ASSERT(balls.matchesSingleElement(match3["a"]));
+    ASSERT(ballc.matchesSingleElement(match1["a"]));
+    ASSERT(ballc.matchesSingleElement(match2["a"]));
+    ASSERT(ballc.matchesSingleElement(match3["a"]));
+    ASSERT(banys.matchesSingleElement(match1["a"]));
+    ASSERT(banys.matchesSingleElement(match2["a"]));
+    ASSERT(banys.matchesSingleElement(match3["a"]));
+    ASSERT(banyc.matchesSingleElement(match1["a"]));
+    ASSERT(banyc.matchesSingleElement(match2["a"]));
+    ASSERT(banyc.matchesSingleElement(match3["a"]));
+}
+
+TEST(BitTestMatchExpression, DoesNotMatchInteger) {
+    BSONArray bas = BSON_ARRAY(1 << 2 << 4 << 5 << 6);
+    BSONArray bac = BSON_ARRAY(0 << 3 << 1);
+    std::vector<uint32_t> bitPositionsSet = bsonArrayToBitPositions(bas);
+    std::vector<uint32_t> bitPositionsClear = bsonArrayToBitPositions(bac);
+
+    BSONObj match1 = fromjson("{a: NumberInt(54)}");
+    BSONObj match2 = fromjson("{a: NumberLong(54)}");
+    BSONObj match3 = fromjson("{a: 54.0}");
+
+    BitsAllSetMatchExpression balls;
+    BitsAllClearMatchExpression ballc;
+    BitsAnySetMatchExpression banys;
+    BitsAnyClearMatchExpression banyc;
+
+    ASSERT_OK(balls.init("a", bitPositionsSet));
+    ASSERT_OK(ballc.init("a", bitPositionsClear));
+    ASSERT_OK(banys.init("a", bitPositionsSet));
+    ASSERT_OK(banyc.init("a", bitPositionsClear));
+    ASSERT_EQ((size_t)5, balls.numBitPositions());
+    ASSERT_EQ((size_t)3, ballc.numBitPositions());
+    ASSERT_EQ((size_t)5, banys.numBitPositions());
+    ASSERT_EQ((size_t)3, banyc.numBitPositions());
+    ASSERT(!balls.matchesSingleElement(match1["a"]));
+    ASSERT(!balls.matchesSingleElement(match2["a"]));
+    ASSERT(!balls.matchesSingleElement(match3["a"]));
+    ASSERT(!ballc.matchesSingleElement(match1["a"]));
+    ASSERT(!ballc.matchesSingleElement(match2["a"]));
+    ASSERT(!ballc.matchesSingleElement(match3["a"]));
+    ASSERT(banys.matchesSingleElement(match1["a"]));
+    ASSERT(banys.matchesSingleElement(match2["a"]));
+    ASSERT(banys.matchesSingleElement(match3["a"]));
+    ASSERT(banyc.matchesSingleElement(match1["a"]));
+    ASSERT(banyc.matchesSingleElement(match2["a"]));
+    ASSERT(banyc.matchesSingleElement(match3["a"]));
+}
+
+TEST(BitTestMatchExpression, DoesNotMatchIntegerWithBitMask) {
+    long long bitMaskSet = 118;
+    long long bitMaskClear = 11;
+
+    BSONObj match1 = fromjson("{a: NumberInt(54)}");
+    BSONObj match2 = fromjson("{a: NumberLong(54)}");
+    BSONObj match3 = fromjson("{a: 54.0}");
+
+    BitsAllSetMatchExpression balls;
+    BitsAllClearMatchExpression ballc;
+    BitsAnySetMatchExpression banys;
+    BitsAnyClearMatchExpression banyc;
+
+    ASSERT_OK(balls.init("a", bitMaskSet));
+    ASSERT_OK(ballc.init("a", bitMaskClear));
+    ASSERT_OK(banys.init("a", bitMaskSet));
+    ASSERT_OK(banyc.init("a", bitMaskClear));
+    ASSERT(!balls.matchesSingleElement(match1["a"]));
+    ASSERT(!balls.matchesSingleElement(match2["a"]));
+    ASSERT(!balls.matchesSingleElement(match3["a"]));
+    ASSERT(!ballc.matchesSingleElement(match1["a"]));
+    ASSERT(!ballc.matchesSingleElement(match2["a"]));
+    ASSERT(!ballc.matchesSingleElement(match3["a"]));
+    ASSERT(banys.matchesSingleElement(match1["a"]));
+    ASSERT(banys.matchesSingleElement(match2["a"]));
+    ASSERT(banys.matchesSingleElement(match3["a"]));
+    ASSERT(banyc.matchesSingleElement(match1["a"]));
+    ASSERT(banyc.matchesSingleElement(match2["a"]));
+    ASSERT(banyc.matchesSingleElement(match3["a"]));
+}
+
+TEST(BitTestMatchExpression, MatchesBinary1) {
+    BSONArray bas = BSON_ARRAY(1 << 2 << 4 << 5);
+    BSONArray bac = BSON_ARRAY(0 << 3 << 600);
+    std::vector<uint32_t> bitPositionsSet = bsonArrayToBitPositions(bas);
+    std::vector<uint32_t> bitPositionsClear = bsonArrayToBitPositions(bac);
+
+    BSONObj match1 = fromjson("{a: {$binary: 'NgAAAAAAAAAAAAAAAAAAAAAAAAAA', $type: '00'}}");
+    // Base64 to Binary: 00110110...
+    BSONObj match2 = fromjson("{a: {$binary: 'NgAjqwetkqwklEWRbWERKKJREtbq', $type: '00'}}");
+    // Base64 to Binary: 00110110...
+
+    BitsAllSetMatchExpression balls;
+    BitsAllClearMatchExpression ballc;
+    BitsAnySetMatchExpression banys;
+    BitsAnyClearMatchExpression banyc;
+
+    ASSERT_OK(balls.init("a", bitPositionsSet));
+    ASSERT_OK(ballc.init("a", bitPositionsClear));
+    ASSERT_OK(banys.init("a", bitPositionsSet));
+    ASSERT_OK(banyc.init("a", bitPositionsClear));
+    ASSERT_EQ((size_t)4, balls.numBitPositions());
+    ASSERT_EQ((size_t)3, ballc.numBitPositions());
+    ASSERT_EQ((size_t)4, banys.numBitPositions());
+    ASSERT_EQ((size_t)3, banyc.numBitPositions());
+    ASSERT(balls.matchesSingleElement(match1["a"]));
+    ASSERT(balls.matchesSingleElement(match2["a"]));
+    ASSERT(ballc.matchesSingleElement(match1["a"]));
+    ASSERT(ballc.matchesSingleElement(match2["a"]));
+    ASSERT(banys.matchesSingleElement(match1["a"]));
+    ASSERT(banys.matchesSingleElement(match2["a"]));
+    ASSERT(banyc.matchesSingleElement(match1["a"]));
+    ASSERT(banyc.matchesSingleElement(match2["a"]));
+}
+
+TEST(BitTestMatchExpression, MatchesBinary2) {
+    BSONArray bas = BSON_ARRAY(21 << 22 << 8 << 9);
+    BSONArray bac = BSON_ARRAY(20 << 23 << 612);
+    std::vector<uint32_t> bitPositionsSet = bsonArrayToBitPositions(bas);
+    std::vector<uint32_t> bitPositionsClear = bsonArrayToBitPositions(bac);
+
+    BSONObj match1 = fromjson("{a: {$binary: 'AANgAAAAAAAAAAAAAAAAAAAAAAAA', $type: '00'}}");
+    // Base64 to Binary: 00000000 00000011 01100000
+    BSONObj match2 = fromjson("{a: {$binary: 'JANgqwetkqwklEWRbWERKKJREtbq', $type: '00'}}");
+    // Base64 to Binary: ........ 00000011 01100000
+
+    BitsAllSetMatchExpression balls;
+    BitsAllClearMatchExpression ballc;
+    BitsAnySetMatchExpression banys;
+    BitsAnyClearMatchExpression banyc;
+
+    ASSERT_OK(balls.init("a", bitPositionsSet));
+    ASSERT_OK(ballc.init("a", bitPositionsClear));
+    ASSERT_OK(banys.init("a", bitPositionsSet));
+    ASSERT_OK(banyc.init("a", bitPositionsClear));
+    ASSERT_EQ((size_t)4, balls.numBitPositions());
+    ASSERT_EQ((size_t)3, ballc.numBitPositions());
+    ASSERT_EQ((size_t)4, banys.numBitPositions());
+    ASSERT_EQ((size_t)3, banyc.numBitPositions());
+    ASSERT(balls.matchesSingleElement(match1["a"]));
+    ASSERT(balls.matchesSingleElement(match2["a"]));
+    ASSERT(ballc.matchesSingleElement(match1["a"]));
+    ASSERT(ballc.matchesSingleElement(match2["a"]));
+    ASSERT(banys.matchesSingleElement(match1["a"]));
+    ASSERT(banys.matchesSingleElement(match2["a"]));
+    ASSERT(banyc.matchesSingleElement(match1["a"]));
+    ASSERT(banyc.matchesSingleElement(match2["a"]));
+}
+
+TEST(BitTestMatchExpression, MatchesBinaryWithBitMask) {
+    const char* bas = "\0\x03\x60\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0";
+    const char* bac = "\0\xFC\x9F\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0";
+
+    BSONObj match1 = fromjson("{a: {$binary: 'AANgAAAAAAAAAAAAAAAAAAAAAAAA', $type: '00'}}");
+    // Base64 to Binary: 00000000 00000011 01100000
+    BSONObj match2 = fromjson("{a: {$binary: 'JANgAwetkqwklEWRbWERKKJREtbq', $type: '00'}}");
+    // Base64 to Binary: ........ 00000011 01100000
+
+    BitsAllSetMatchExpression balls;
+    BitsAllClearMatchExpression ballc;
+    BitsAnySetMatchExpression banys;
+    BitsAnyClearMatchExpression banyc;
+    ASSERT_OK(balls.init("a", bas, 21));
+    ASSERT_OK(ballc.init("a", bac, 21));
+    ASSERT_OK(banys.init("a", bas, 21));
+    ASSERT_OK(banyc.init("a", bac, 21));
+    ASSERT(balls.matchesSingleElement(match1["a"]));
+    ASSERT(balls.matchesSingleElement(match2["a"]));
+    ASSERT(ballc.matchesSingleElement(match1["a"]));
+    ASSERT(ballc.matchesSingleElement(match2["a"]));
+    ASSERT(banys.matchesSingleElement(match1["a"]));
+    ASSERT(banys.matchesSingleElement(match2["a"]));
+    ASSERT(banyc.matchesSingleElement(match1["a"]));
+    ASSERT(banyc.matchesSingleElement(match2["a"]));
+}
+
+TEST(BitTestMatchExpression, DoesNotMatchBinary1) {
+    BSONArray bas = BSON_ARRAY(1 << 2 << 4 << 5 << 6);
+    BSONArray bac = BSON_ARRAY(0 << 3 << 1);
+    std::vector<uint32_t> bitPositionsSet = bsonArrayToBitPositions(bas);
+    std::vector<uint32_t> bitPositionsClear = bsonArrayToBitPositions(bac);
+
+    BSONObj match1 = fromjson("{a: {$binary: 'NgAAAAAAAAAAAAAAAAAAAAAAAAAA', $type: '00'}}");
+    // Base64 to Binary: 00110110...
+    BSONObj match2 = fromjson("{a: {$binary: 'NgAjqwetkqwklEWRbWERKKJREtbq', $type: '00'}}");
+    // Base64 to Binary: 00110110...
+
+    BitsAllSetMatchExpression balls;
+    BitsAllClearMatchExpression ballc;
+    BitsAnySetMatchExpression banys;
+    BitsAnyClearMatchExpression banyc;
+
+    ASSERT_OK(balls.init("a", bitPositionsSet));
+    ASSERT_OK(ballc.init("a", bitPositionsClear));
+    ASSERT_OK(banys.init("a", bitPositionsSet));
+    ASSERT_OK(banyc.init("a", bitPositionsClear));
+    ASSERT_EQ((size_t)5, balls.numBitPositions());
+    ASSERT_EQ((size_t)3, ballc.numBitPositions());
+    ASSERT_EQ((size_t)5, banys.numBitPositions());
+    ASSERT_EQ((size_t)3, banyc.numBitPositions());
+    ASSERT(!balls.matchesSingleElement(match1["a"]));
+    ASSERT(!balls.matchesSingleElement(match2["a"]));
+    ASSERT(!ballc.matchesSingleElement(match1["a"]));
+    ASSERT(!ballc.matchesSingleElement(match2["a"]));
+    ASSERT(banys.matchesSingleElement(match1["a"]));
+    ASSERT(banys.matchesSingleElement(match2["a"]));
+    ASSERT(banyc.matchesSingleElement(match1["a"]));
+    ASSERT(banyc.matchesSingleElement(match2["a"]));
+}
+
+TEST(BitTestMatchExpression, DoesNotMatchBinary2) {
+    BSONArray bas = BSON_ARRAY(21 << 22 << 23 << 24 << 25);
+    BSONArray bac = BSON_ARRAY(20 << 23 << 21);
+    std::vector<uint32_t> bitPositionsSet = bsonArrayToBitPositions(bas);
+    std::vector<uint32_t> bitPositionsClear = bsonArrayToBitPositions(bac);
+
+    BSONObj match1 = fromjson("{a: {$binary: 'AANgAAAAAAAAAAAAAAAAAAAAAAAA', $type: '00'}}");
+    // Base64 to Binary: 00000000 00000011 01100000
+    BSONObj match2 = fromjson("{a: {$binary: 'JANgqwetkqwklEWRbWERKKJREtbq', $type: '00'}}");
+    // Base64 to Binary: ........ 00000011 01100000
+
+    BitsAllSetMatchExpression balls;
+    BitsAllClearMatchExpression ballc;
+    BitsAnySetMatchExpression banys;
+    BitsAnyClearMatchExpression banyc;
+
+    ASSERT_OK(balls.init("a", bitPositionsSet));
+    ASSERT_OK(ballc.init("a", bitPositionsClear));
+    ASSERT_OK(banys.init("a", bitPositionsSet));
+    ASSERT_OK(banyc.init("a", bitPositionsClear));
+    ASSERT_EQ((size_t)5, balls.numBitPositions());
+    ASSERT_EQ((size_t)3, ballc.numBitPositions());
+    ASSERT_EQ((size_t)5, banys.numBitPositions());
+    ASSERT_EQ((size_t)3, banyc.numBitPositions());
+    ASSERT(!balls.matchesSingleElement(match1["a"]));
+    ASSERT(!balls.matchesSingleElement(match2["a"]));
+    ASSERT(!ballc.matchesSingleElement(match1["a"]));
+    ASSERT(!ballc.matchesSingleElement(match2["a"]));
+    ASSERT(banys.matchesSingleElement(match1["a"]));
+    ASSERT(banys.matchesSingleElement(match2["a"]));
+    ASSERT(banyc.matchesSingleElement(match1["a"]));
+    ASSERT(banyc.matchesSingleElement(match2["a"]));
+}
+
+TEST(BitTestMatchExpression, DoesNotMatchBinaryWithBitMask) {
+    const char* bas = "\0\x03\x60\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\xFF";
+    const char* bac = "\0\xFD\x9F\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\xFF";
+
+    BSONObj match1 = fromjson("{a: {$binary: 'AANgAAAAAAAAAAAAAAAAAAAAAAAA', $type: '00'}}");
+    // Base64 to Binary: 00000000 00000011 01100000
+    BSONObj match2 = fromjson("{a: {$binary: 'JANgAwetkqwklEWRbWERKKJREtbq', $type: '00'}}");
+    // Base64 to Binary: ........ 00000011 01100000
+
+    BitsAllSetMatchExpression balls;
+    BitsAllClearMatchExpression ballc;
+    BitsAnySetMatchExpression banys;
+    BitsAnyClearMatchExpression banyc;
+    ASSERT_OK(balls.init("a", bas, 22));
+    ASSERT_OK(ballc.init("a", bac, 22));
+    ASSERT_OK(banys.init("a", bas, 22));
+    ASSERT_OK(banyc.init("a", bac, 22));
+    ASSERT(!balls.matchesSingleElement(match1["a"]));
+    ASSERT(!balls.matchesSingleElement(match2["a"]));
+    ASSERT(!ballc.matchesSingleElement(match1["a"]));
+    ASSERT(!ballc.matchesSingleElement(match2["a"]));
+    ASSERT(banys.matchesSingleElement(match1["a"]));
+    ASSERT(banys.matchesSingleElement(match2["a"]));
+    ASSERT(banyc.matchesSingleElement(match1["a"]));
+    ASSERT(banyc.matchesSingleElement(match2["a"]));
+}
 }
diff --git a/src/mongo/db/matcher/expression_parser.cpp b/src/mongo/db/matcher/expression_parser.cpp
index 46a0c8520cf..b0091234bc9 100644
--- a/src/mongo/db/matcher/expression_parser.cpp
+++ b/src/mongo/db/matcher/expression_parser.cpp
@@ -64,6 +64,7 @@ bool hasNode(const MatchExpression* root, MatchExpression::MatchType type) {
 namespace mongo {
 
 using std::string;
+using stdx::make_unique;
 
 StatusWithMatchExpression MatchExpressionParser::_parseComparison(const char* name,
                                                                   ComparisonMatchExpression* cmp,
@@ -73,9 +74,9 @@ StatusWithMatchExpression MatchExpressionParser::_parseComparison(const char* na
     // Non-equality comparison match expressions cannot have
     // a regular expression as the argument (e.g. {a: {$gt: /b/}} is illegal).
     if (MatchExpression::EQ != cmp->matchType() && RegEx == e.type()) {
-        std::stringstream ss;
+        mongoutils::str::stream ss;
         ss << "Can't have RegEx as arg to predicate over field '" << name << "'.";
-        return {Status(ErrorCodes::BadValue, ss.str())};
+        return {Status(ErrorCodes::BadValue, ss)};
     }
 
     Status s = temp->init(name, e);
@@ -249,6 +250,24 @@ StatusWithMatchExpression MatchExpressionParser::_parseSubField(const BSONObj& c
         case BSONObj::opWITHIN:
         case BSONObj::opGEO_INTERSECTS:
             return expressionParserGeoCallback(name, x, context);
+
+        // Handles bitwise query operators.
+
+        case BSONObj::opBITS_ALL_SET: {
+            return _parseBitTest<BitsAllSetMatchExpression>(name, e);
+        }
+
+        case BSONObj::opBITS_ALL_CLEAR: {
+            return _parseBitTest<BitsAllClearMatchExpression>(name, e);
+        }
+
+        case BSONObj::opBITS_ANY_SET: {
+            return _parseBitTest<BitsAnySetMatchExpression>(name, e);
+        }
+
+        case BSONObj::opBITS_ANY_CLEAR: {
+            return _parseBitTest<BitsAnyClearMatchExpression>(name, e);
+        }
     }
 
     return {Status(ErrorCodes::BadValue,
@@ -789,6 +808,151 @@ StatusWithMatchExpression MatchExpressionParser::_parseAll(const char* name,
     return {std::move(myAnd)};
 }
 
+template <class T>
+StatusWithMatchExpression MatchExpressionParser::_parseBitTest(const char* name,
+                                                               const BSONElement& e) {
+    std::unique_ptr<BitTestMatchExpression> bitTestMatchExpression = stdx::make_unique<T>();
+
+    if (e.type() == BSONType::Array) {
+        // Array of bit positions provided as value.
+        auto statusWithBitPositions = _parseBitPositionsArray(e.Obj());
+        if (!statusWithBitPositions.isOK()) {
+            return statusWithBitPositions.getStatus();
+        }
+
+        std::vector<uint32_t> bitPositions = statusWithBitPositions.getValue();
+        Status s = bitTestMatchExpression->init(name, bitPositions);
+        if (!s.isOK()) {
+            return s;
+        }
+    } else if (e.isNumber()) {
+        // Integer bitmask provided as value.
+
+        if (e.type() == BSONType::NumberDouble) {
+            double eDouble = e.numberDouble();
+
+            // NaN doubles are rejected.
+            if (std::isnan(eDouble)) {
+                mongoutils::str::stream ss;
+                ss << name << " cannot take a NaN";
+                return Status(ErrorCodes::BadValue, ss);
+            }
+
+            // No integral doubles that are too large to be represented as a 64 bit signed integer.
+            // We use 'kLongLongMaxAsDouble' because if we just did eDouble > 2^63-1, it would be
+            // compared against 2^63. eDouble=2^63 would not get caught that way.
+            if (eDouble >= BitTestMatchExpression::kLongLongMaxPlusOneAsDouble ||
+                eDouble < std::numeric_limits<long long>::min()) {
+                mongoutils::str::stream ss;
+                ss << name << " cannot be represented as a 64-bit integer: " << e;
+                return Status(ErrorCodes::BadValue, ss);
+            }
+
+            // This checks if e is an integral double.
+            if (eDouble != static_cast<double>(static_cast<long long>(eDouble))) {
+                mongoutils::str::stream ss;
+                ss << name << " cannot have a fractional part but received: " << e;
+                return Status(ErrorCodes::BadValue, ss);
+            }
+        }
+
+        long long bitMask = e.numberLong();
+
+        // No negatives.
+        if (bitMask < 0) {
+            mongoutils::str::stream ss;
+            ss << name << " cannot take a negative number: " << e;
+            return Status(ErrorCodes::BadValue, ss);
+        }
+
+        Status s = bitTestMatchExpression->init(name, bitMask);
+        if (!s.isOK()) {
+            return s;
+        }
+    } else if (e.type() == BSONType::BinData) {
+        // Binary bitmask provided as value.
+
+        int eBinaryLen;
+        const char* eBinary = e.binData(eBinaryLen);
+
+        Status s = bitTestMatchExpression->init(name, eBinary, eBinaryLen);
+        if (!s.isOK()) {
+            return s;
+        }
+    } else {
+        mongoutils::str::stream ss;
+        ss << name << " takes an Array, a number, or a BinData but received: " << e;
+        return Status(ErrorCodes::BadValue, ss);
+    }
+
+    return {std::move(bitTestMatchExpression)};
+}
+
+StatusWith<std::vector<uint32_t>> MatchExpressionParser::_parseBitPositionsArray(
+    const BSONObj& theArray) {
+    std::vector<uint32_t> bitPositions;
+
+    // Fill temporary bit position array with integers read from the BSON array.
+    for (const BSONElement& e : theArray) {
+        if (!e.isNumber()) {
+            mongoutils::str::stream ss;
+            ss << "bit positions must be an integer but got: " << e;
+            return Status(ErrorCodes::BadValue, ss);
+        }
+
+        if (e.type() == BSONType::NumberDouble) {
+            double eDouble = e.numberDouble();
+
+            // NaN doubles are rejected.
+            if (std::isnan(eDouble)) {
+                mongoutils::str::stream ss;
+                ss << "bit positions cannot take a NaN: " << e;
+                return Status(ErrorCodes::BadValue, ss);
+            }
+
+            // This makes sure e does not overflow a 32-bit integer container.
+            if (eDouble > std::numeric_limits<int>::max() ||
+                eDouble < std::numeric_limits<int>::min()) {
+                mongoutils::str::stream ss;
+                ss << "bit positions cannot be represented as a 32-bit signed integer: " << e;
+                return Status(ErrorCodes::BadValue, ss);
+            }
+
+            // This checks if e is integral.
+            if (eDouble != static_cast<double>(static_cast<long long>(eDouble))) {
+                mongoutils::str::stream ss;
+                ss << "bit positions must be an integer but got: " << e;
+                return Status(ErrorCodes::BadValue, ss);
+            }
+        }
+
+        if (e.type() == BSONType::NumberLong) {
+            long long eLong = e.numberLong();
+
+            // This makes sure e does not overflow a 32-bit integer container.
+            if (eLong > std::numeric_limits<int>::max() ||
+                eLong < std::numeric_limits<int>::min()) {
+                mongoutils::str::stream ss;
+                ss << "bit positions cannot be represented as a 32-bit signed integer: " << e;
+                return Status(ErrorCodes::BadValue, ss);
+            }
+        }
+
+        int eValue = e.numberInt();
+
+        // No negatives.
+        if (eValue < 0) {
+            mongoutils::str::stream ss;
+            ss << "bit positions must be >= 0 but got: " << e;
+            return Status(ErrorCodes::BadValue, ss);
+        }
+
+        bitPositions.push_back(eValue);
+    }
+
+    return bitPositions;
+}
+
 StatusWithMatchExpression MatchExpressionParser::WhereCallback::parseWhere(
     const BSONElement& where) const {
     return {Status(ErrorCodes::NoWhereParseContext, "no context for parsing $where")};
diff --git a/src/mongo/db/matcher/expression_parser.h b/src/mongo/db/matcher/expression_parser.h
index e9bb3cf7200..fd9500801b4 100644
--- a/src/mongo/db/matcher/expression_parser.h
+++ b/src/mongo/db/matcher/expression_parser.h
@@ -148,6 +148,17 @@ private:
 
     StatusWithMatchExpression _parseNot(const char* name, const BSONElement& e, int level);
 
+    /**
+     * Parses 'e' into a BitTestMatchExpression.
+     */
+    template <class T>
+    StatusWithMatchExpression _parseBitTest(const char* name, const BSONElement& e);
+
+    /**
+     * Converts 'theArray', a BSONArray of integers, into a std::vector of integers.
+     */
+    StatusWith<std::vector<uint32_t>> _parseBitPositionsArray(const BSONObj& theArray);
+
     // The maximum allowed depth of a query tree. Just to guard against stack overflow.
     static const int kMaximumTreeDepth;
 
diff --git a/src/mongo/db/matcher/expression_parser_leaf_test.cpp b/src/mongo/db/matcher/expression_parser_leaf_test.cpp
index 2d1dd80cc26..e6cad775ad7 100644
--- a/src/mongo/db/matcher/expression_parser_leaf_test.cpp
+++ b/src/mongo/db/matcher/expression_parser_leaf_test.cpp
@@ -750,4 +750,273 @@ TEST(MatchExpressionParserLeafTest, TypeStringnameNumber) {
     ASSERT_TRUE(tmeNumber->matchesBSON(BSON("a" << -1LL)));
     ASSERT_FALSE(tmeNumber->matchesBSON(fromjson("{a: ''}")));
 }
+
+TEST(MatchExpressionParserTest, BitTestMatchExpressionValidMask) {
+    const double k2Power53 = scalbn(1, 32);
+
+    ASSERT_OK(MatchExpressionParser::parse(BSON("a" << BSON("$bitsAllSet" << 54))).getStatus());
+    ASSERT_OK(
+        MatchExpressionParser::parse(
+            BSON("a" << BSON("$bitsAllSet" << std::numeric_limits<long long>::max()))).getStatus());
+    ASSERT_OK(
+        MatchExpressionParser::parse(BSON("a" << BSON("$bitsAllSet" << k2Power53))).getStatus());
+    ASSERT_OK(MatchExpressionParser::parse(BSON("a" << BSON("$bitsAllSet" << k2Power53 - 1)))
+                  .getStatus());
+
+    ASSERT_OK(MatchExpressionParser::parse(BSON("a" << BSON("$bitsAllClear" << 54))).getStatus());
+    ASSERT_OK(MatchExpressionParser::parse(
+                  BSON("a" << BSON("$bitsAllClear" << std::numeric_limits<long long>::max())))
+                  .getStatus());
+    ASSERT_OK(
+        MatchExpressionParser::parse(BSON("a" << BSON("$bitsAllClear" << k2Power53))).getStatus());
+    ASSERT_OK(MatchExpressionParser::parse(BSON("a" << BSON("$bitsAllClear" << k2Power53 - 1)))
+                  .getStatus());
+
+    ASSERT_OK(MatchExpressionParser::parse(BSON("a" << BSON("$bitsAnySet" << 54))).getStatus());
+    ASSERT_OK(
+        MatchExpressionParser::parse(
+            BSON("a" << BSON("$bitsAnySet" << std::numeric_limits<long long>::max()))).getStatus());
+    ASSERT_OK(
+        MatchExpressionParser::parse(BSON("a" << BSON("$bitsAnySet" << k2Power53))).getStatus());
+    ASSERT_OK(MatchExpressionParser::parse(BSON("a" << BSON("$bitsAnySet" << k2Power53 - 1)))
+                  .getStatus());
+
+    ASSERT_OK(MatchExpressionParser::parse(BSON("a" << BSON("$bitsAnyClear" << 54))).getStatus());
+    ASSERT_OK(MatchExpressionParser::parse(
+                  BSON("a" << BSON("$bitsAnyClear" << std::numeric_limits<long long>::max())))
+                  .getStatus());
+    ASSERT_OK(
+        MatchExpressionParser::parse(BSON("a" << BSON("$bitsAnyClear" << k2Power53))).getStatus());
+    ASSERT_OK(MatchExpressionParser::parse(BSON("a" << BSON("$bitsAnyClear" << k2Power53 - 1)))
+                  .getStatus());
+}
+
+TEST(MatchExpressionParserTest, BitTestMatchExpressionValidArray) {
+    ASSERT_OK(MatchExpressionParser::parse(BSON("a" << BSON("$bitsAllSet" << BSON_ARRAY(0))))
+                  .getStatus());
+    ASSERT_OK(MatchExpressionParser::parse(
+                  BSON("a" << BSON("$bitsAllSet" << BSON_ARRAY(0 << 1 << 2 << 3)))).getStatus());
+    ASSERT_OK(MatchExpressionParser::parse(
+                  BSON("a" << BSON("$bitsAllSet" << BSON_ARRAY(std::numeric_limits<int>::max()))))
+                  .getStatus());
+
+    ASSERT_OK(MatchExpressionParser::parse(BSON("a" << BSON("$bitsAllClear" << BSON_ARRAY(0))))
+                  .getStatus());
+    ASSERT_OK(MatchExpressionParser::parse(
+                  BSON("a" << BSON("$bitsAllClear" << BSON_ARRAY(0 << 1 << 2 << 3)))).getStatus());
+    ASSERT_OK(MatchExpressionParser::parse(
+                  BSON("a" << BSON("$bitsAllClear" << BSON_ARRAY(std::numeric_limits<int>::max()))))
+                  .getStatus());
+
+    ASSERT_OK(MatchExpressionParser::parse(BSON("a" << BSON("$bitsAnySet" << BSON_ARRAY(0))))
+                  .getStatus());
+    ASSERT_OK(MatchExpressionParser::parse(
+                  BSON("a" << BSON("$bitsAnySet" << BSON_ARRAY(0 << 1 << 2 << 3)))).getStatus());
+    ASSERT_OK(MatchExpressionParser::parse(
+                  BSON("a" << BSON("$bitsAnySet" << BSON_ARRAY(std::numeric_limits<int>::max()))))
+                  .getStatus());
+
+    ASSERT_OK(MatchExpressionParser::parse(BSON("a" << BSON("$bitsAnyClear" << BSON_ARRAY(0))))
+                  .getStatus());
+    ASSERT_OK(MatchExpressionParser::parse(
+                  BSON("a" << BSON("$bitsAnyClear" << BSON_ARRAY(0 << 1 << 2 << 3)))).getStatus());
+    ASSERT_OK(MatchExpressionParser::parse(
+                  BSON("a" << BSON("$bitsAnyClear" << BSON_ARRAY(std::numeric_limits<int>::max()))))
+                  .getStatus());
+}
+
+TEST(MatchExpressionParserTest, BitTestMatchExpressionValidBinData) {
+    ASSERT_OK(
+        MatchExpressionParser::parse(
+            fromjson("{a: {$bitsAllSet: {$binary: 'AAAAAAAAAAAAAAAAAAAAAAAAAAAA', $type: '00'}}}"))
+            .getStatus());
+
+    ASSERT_OK(
+        MatchExpressionParser::parse(
+            fromjson(
+                "{a: {$bitsAllClear: {$binary: 'AAAAAAAAAAAAAAAAAAAAAAAAAAAA', $type: '00'}}}"))
+            .getStatus());
+
+    ASSERT_OK(
+        MatchExpressionParser::parse(
+            fromjson("{a: {$bitsAnySet: {$binary: 'AAAAAAAAAAAAAAAAAAAAAAAAAAAA', $type: '00'}}}"))
+            .getStatus());
+
+    ASSERT_OK(
+        MatchExpressionParser::parse(
+            fromjson(
+                "{a: {$bitsAnyClear: {$binary: 'AAAAAAAAAAAAAAAAAAAAAAAAAAAA', $type: '00'}}}"))
+            .getStatus());
+}
+
+TEST(MatchExpressionParserTest, BitTestMatchExpressionInvalidMaskType) {
+    ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAllSet: null}}")).getStatus());
+    ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAllSet: true}}")).getStatus());
+    ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAllSet: {}}}")).getStatus());
+    ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAllSet: ''}}")).getStatus());
+
+    ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAllClear: null}}")).getStatus());
+    ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAllClear: true}}")).getStatus());
+    ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAllClear: {}}}")).getStatus());
+    ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAllClear: ''}}")).getStatus());
+    ASSERT_NOT_OK(
+        MatchExpressionParser::parse(
+            fromjson("{a: {$bitsAllClear: ObjectId('000000000000000000000000')}}")).getStatus());
+
+    ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAnySet: null}}")).getStatus());
+    ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAnySet: true}}")).getStatus());
+    ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAnySet: {}}}")).getStatus());
+    ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAnySet: ''}}")).getStatus());
+    ASSERT_NOT_OK(
+        MatchExpressionParser::parse(
+            fromjson("{a: {$bitsAnySet: ObjectId('000000000000000000000000')}}")).getStatus());
+
+    ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAnyClear: null}}")).getStatus());
+    ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAnyClear: true}}")).getStatus());
+    ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAnyClear: {}}}")).getStatus());
+    ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAnyClear: ''}}")).getStatus());
+    ASSERT_NOT_OK(
+        MatchExpressionParser::parse(
+            fromjson("{a: {$bitsAnyClear: ObjectId('000000000000000000000000')}}")).getStatus());
+}
+
+TEST(MatchExpressionParserTest, BitTestMatchExpressionInvalidMaskValue) {
+    const double kLongLongMaxAsDouble = scalbn(1, std::numeric_limits<long long>::digits);
+
+    ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAllSet: NaN}}")).getStatus());
+    ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAllSet: -54}}")).getStatus());
+    ASSERT_NOT_OK(
+        MatchExpressionParser::parse(
+            BSON("a" << BSON("$bitsAllSet" << std::numeric_limits<double>::max()))).getStatus());
+    ASSERT_NOT_OK(MatchExpressionParser::parse(
+                      BSON("a" << BSON("$bitsAllSet" << kLongLongMaxAsDouble))).getStatus());
+    ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAllSet: 2.5}}")).getStatus());
+
+    ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAllClear: NaN}}")).getStatus());
+    ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAllClear: -54}}")).getStatus());
+    ASSERT_NOT_OK(
+        MatchExpressionParser::parse(
+            BSON("a" << BSON("$bitsAllClear" << std::numeric_limits<double>::max()))).getStatus());
+    ASSERT_NOT_OK(MatchExpressionParser::parse(
+                      BSON("a" << BSON("$bitsAllClear" << kLongLongMaxAsDouble))).getStatus());
+    ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAllClear: 2.5}}")).getStatus());
+
+    ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAnySet: NaN}}")).getStatus());
+    ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAnySet: -54}}")).getStatus());
+    ASSERT_NOT_OK(
+        MatchExpressionParser::parse(
+            BSON("a" << BSON("$bitsAnySet" << std::numeric_limits<double>::max()))).getStatus());
+    ASSERT_NOT_OK(MatchExpressionParser::parse(
+                      BSON("a" << BSON("$bitsAnySet" << kLongLongMaxAsDouble))).getStatus());
+    ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAnySet: 2.5}}")).getStatus());
+
+    ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAnyClear: NaN}}")).getStatus());
+    ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAnyClear: -54}}")).getStatus());
+    ASSERT_NOT_OK(
+        MatchExpressionParser::parse(
+            BSON("a" << BSON("$bitsAnyClear" << std::numeric_limits<double>::max()))).getStatus());
+    ASSERT_NOT_OK(MatchExpressionParser::parse(
+                      BSON("a" << BSON("$bitsAnyClear" << kLongLongMaxAsDouble))).getStatus());
+    ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAnyClear: 2.5}}")).getStatus());
+}
+
+TEST(MatchExpressionParserTest, BitTestMatchExpressionInvalidArray) {
+    ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAllSet: [null]}}")).getStatus());
+    ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAllSet: [true]}}")).getStatus());
+    ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAllSet: ['']}}")).getStatus());
+    ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAllSet: [{}]}}")).getStatus());
+    ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAllSet: [[]]}}")).getStatus());
+    ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAllSet: [-1]}}")).getStatus());
+    ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAllSet: [2.5]}}")).getStatus());
+    ASSERT_NOT_OK(
+        MatchExpressionParser::parse(
+            fromjson(
+                "{a: {$bitsAllSet: [{$binary: 'AAAAAAAAAAAAAAAAAAAAAAAAAAAA', $type: '00'}]}}"))
+            .getStatus());
+
+    ASSERT_NOT_OK(
+        MatchExpressionParser::parse(fromjson("{a: {$bitsAllClear: [null]}}")).getStatus());
+    ASSERT_NOT_OK(
+        MatchExpressionParser::parse(fromjson("{a: {$bitsAllClear: [true]}}")).getStatus());
+    ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAllClear: ['']}}")).getStatus());
+    ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAllClear: [{}]}}")).getStatus());
+    ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAllClear: [[]]}}")).getStatus());
+    ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAllClear: [-1]}}")).getStatus());
+    ASSERT_NOT_OK(
+        MatchExpressionParser::parse(fromjson("{a: {$bitsAllClear: [2.5]}}")).getStatus());
+    ASSERT_NOT_OK(
+        MatchExpressionParser::parse(
+            fromjson(
+                "{a: {$bitsAllClear: [{$binary: 'AAAAAAAAAAAAAAAAAAAAAAAAAAAA', $type: '00'}]}}"))
+            .getStatus());
+
+    ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAnySet: [null]}}")).getStatus());
+    ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAnySet: [true]}}")).getStatus());
+    ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAnySet: ['']}}")).getStatus());
+    ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAnySet: [{}]}}")).getStatus());
+    ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAnySet: [[]]}}")).getStatus());
+    ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAnySet: [-1]}}")).getStatus());
+    ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAnySet: [2.5]}}")).getStatus());
+    ASSERT_NOT_OK(
+        MatchExpressionParser::parse(
+            fromjson(
+                "{a: {$bitsAnySet: [{$binary: 'AAAAAAAAAAAAAAAAAAAAAAAAAAAA', $type: '00'}]}}"))
+            .getStatus());
+
+    ASSERT_NOT_OK(
+        MatchExpressionParser::parse(fromjson("{a: {$bitsAnyClear: [null]}}")).getStatus());
+    ASSERT_NOT_OK(
+        MatchExpressionParser::parse(fromjson("{a: {$bitsAnyClear: [true]}}")).getStatus());
+    ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAnyClear: ['']}}")).getStatus());
+    ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAnyClear: [{}]}}")).getStatus());
+    ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAnyClear: [[]]}}")).getStatus());
+    ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAnyClear: [-1]}}")).getStatus());
+    ASSERT_NOT_OK(
+        MatchExpressionParser::parse(fromjson("{a: {$bitsAnyClear: [2.5]}}")).getStatus());
+    ASSERT_NOT_OK(
+        MatchExpressionParser::parse(
+            fromjson(
+                "{a: {$bitsAnyClear: [{$binary: 'AAAAAAAAAAAAAAAAAAAAAAAAAAAA', $type: '00'}]}}"))
+            .getStatus());
+}
+
+TEST(MatchExpressionParserTest, BitTestMatchExpressionInvalidArrayValue) {
+    ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAllSet: [-54]}}")).getStatus());
+    ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAllSet: [NaN]}}")).getStatus());
+    ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAllSet: [2.5]}}")).getStatus());
+    ASSERT_NOT_OK(
+        MatchExpressionParser::parse(
+            BSON("a" << BSON("$bitsAllSet" << BSON_ARRAY(std::numeric_limits<long long>::max()))))
+            .getStatus());
+
+    ASSERT_NOT_OK(
+        MatchExpressionParser::parse(fromjson("{a: {$bitsAllClear: [-54]}}")).getStatus());
+    ASSERT_NOT_OK(
+        MatchExpressionParser::parse(fromjson("{a: {$bitsAllClear: [NaN]}}")).getStatus());
+    ASSERT_NOT_OK(
+        MatchExpressionParser::parse(fromjson("{a: {$bitsAllClear: [2.5]}}")).getStatus());
+    ASSERT_NOT_OK(
+        MatchExpressionParser::parse(
+            BSON("a" << BSON("$bitsAllClear" << BSON_ARRAY(std::numeric_limits<long long>::max()))))
+            .getStatus());
+
+    ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAnySet: [-54]}}")).getStatus());
+    ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAnySet: [NaN]}}")).getStatus());
+    ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAnySet: [2.5]}}")).getStatus());
+    ASSERT_NOT_OK(
+        MatchExpressionParser::parse(
+            BSON("a" << BSON("$bitsAnySet" << BSON_ARRAY(std::numeric_limits<long long>::max()))))
+            .getStatus());
+
+    ASSERT_NOT_OK(
+        MatchExpressionParser::parse(fromjson("{a: {$bitsAnyClear: [-54]}}")).getStatus());
+    ASSERT_NOT_OK(
+        MatchExpressionParser::parse(fromjson("{a: {$bitsAnyClear: [NaN]}}")).getStatus());
+    ASSERT_NOT_OK(
+        MatchExpressionParser::parse(fromjson("{a: {$bitsAnyClear: [2.5]}}")).getStatus());
+    ASSERT_NOT_OK(
+        MatchExpressionParser::parse(
+            BSON("a" << BSON("$bitsAnyClear" << BSON_ARRAY(std::numeric_limits<long long>::max()))))
+            .getStatus());
+}
 }