This is way over my head, but as a proof of concept, I tried to use Bit::Vector to compare the needle and haystack as strings. Probably not very efficient for the large sets you're talking about.
#!perl
use strict;
use warnings;
use Bit::Vector;
# 101001
my $nedInHay = Bit::Vector->new_Dec(6, 41);
# 101000
my $nedNOTInHay = Bit::Vector->new_Dec(6, 40);
# 100101001001000011111010
my $hay = Bit::Vector->new_Dec(24, 9736442);
print $nedInHay->to_Bin;
if ((my $idx = index ($hay->to_Bin, $nedInHay->to_Bin )) != -1) {
print " Found. Starts at position - $idx\n"
}
print $nedNOTInHay->to_Bin;
if (my $idx = index ($hay->to_Bin, $nedNOTInHay->to_Bin ) != -1) {
print " Found. Starts at position - $idx\n"
}
print "\n"
... and run ...
VinsWorldcom@C:\Users\VinsWorldcom\tmp> test.pl
101001 Found. Starts at position - 3
101000