How can I count the number of times a byte sequence occurs in a file?

This is the one-liner solution requested (for recent shells that have "process substitution"):

grep -o "ef be ad de" <(hexdump -v -e '/1 "%02x "' infile.bin) | wc -l

If no "process substitution" <(…) is available, just use grep as a filter:

hexdump -v -e '/1 "%02x "' infile.bin  | grep -o "ef be ad de" | wc -l

Below is the detailed description of each part of the solution.

Byte values from hex numbers:

Your first problem is easy to resolve:

Those \Xnn escape sequences only work in the fish shell.

Change the upper X to a lower one x and use printf (for most shells):

$ printf -- '\xef\xbe\xad\xde'

Or use:

$ /usr/bin/printf -- '\xef\xbe\xad\xde'

For those shells that choose to not implement the '\x' representation.

Of course, translating hex to octal will work on (almost) any shell:

$ "$sh" -c 'printf '\''%b'\'' "$(printf '\''\\0%o'\'' $((0xef)) $((0xbe)) $((0xad)) $((0xde)) )"'

Where "$sh" is any (reasonable) shell. But it is quite difficult to keep it correctly quoted.

Binary files.

The most robust solution is to transform the file and the byte sequence (both) to some encoding that has no issues with odd character values like (new line) 0x0A or (null byte) 0x00. Both are quite difficult to manage correctly with tools designed and adapted to process "text files".

A transformation like base64 may seem a valid one, but it presents the issue that every input byte may have up to three output representations depending if it is the first, second or third byte of the mod 24 (bits) position.

$ echo "abc" | base64
YWJjCg==

$ echo "-abc" | base64
LWFiYwo=

$ echo "--abc" | base64
LS1hYmMK

$ echo "---abc" | base64        # Note that YWJj repeats.
LS0tYWJjCg==

Hex transform.

Thats why the most robust transformation should be one that starts on each byte boundary, like the simple HEX representation.
We can get a file with the hex representation of the file with either any of this tools:

$ od -vAn -tx1 infile.bin | tr -d '\n'   > infile.hex
$ hexdump -v -e '/1 "%02x "' infile.bin  > infile.hex
$ xxd -c1 -p infile.bin | tr '\n' ' '    > infile.hex

The byte sequence to search is already in hex in this case.
:

$ var="ef be ad de"

But it could also be transformed. An example of a round trip hex-bin-hex follows:

$ echo "ef be ad de" | xxd -p -r | od -vAn -tx1
ef be ad de

The search string may be set from the binary representation. Any of the three options presented above od, hexdump, or xxd are equivalent. Just make sure to include the spaces to ensure the match is on byte boundaries (no nibble shift allowed):

$ a="$(printf "\xef\xbe\xad\xde" | hexdump -v -e '/1 "%02x "')"
$ echo "$a"
ef be ad de

If the binary file looks like this:

$ cat infile.bin | xxd
00000000: 5468 6973 2069 7320 efbe adde 2061 2074  This is .... a t
00000010: 6573 7420 0aef bead de0a 6f66 2069 6e70  est ......of inp
00000020: 7574 200a dead beef 0a66 726f 6d20 6120  ut ......from a 
00000030: 6269 0a6e 6172 7920 6669 6c65 2e0a 3131  bi.nary file..11
00000040: 3232 3131 3232 3131 3232 3131 3232 3131  2211221122112211
00000050: 3232 3131 3232 3131 3232 3131 3232 3131  2211221122112211
00000060: 3232 0a

Then, a simple grep search will give the list of matched sequences:

$ grep -o "$a" infile.hex | wc -l
2

One Line?

It all may be performed in one line:

$ grep -o "ef be ad de" <(xxd -c 1 -p infile.bin | tr '\n' ' ') | wc -l

For example, searching for 11221122 in the same file will need this two steps:

$ a="$(printf '11221122' | hexdump -v -e '/1 "%02x "')"
$ grep -o "$a" <(xxd -c1 -p infile.bin | tr '\n' ' ') | wc -l
4

To "see" the matches:

$ grep -o "$a" <(xxd -c1 -p infile.bin | tr '\n' ' ')
3131323231313232
3131323231313232
3131323231313232
3131323231313232

$ grep "$a" <(xxd -c1 -p infile.bin | tr '\n' ' ')

… 0a 3131323231313232313132323131323231313232313132323131323231313232 313132320a

---

Buffering

There is a concern that grep will buffer the whole file, and, if the file is big, create a heavy load for the computer. For that, we may use an unbuffered sed solution:

a='ef be ad de'
hexdump -v -e '/1 "%02x "' infile.bin  | 
    sed -ue 's/\('"$a"'\)/\n\1\n/g' | 
        sed -n '/^'"$a"'$/p' |
            wc -l

The first sed is unbuffered (-u) and is used only to inject two newlines on the stream per matching string. The second sed will only print the (short) matching lines. The wc -l will count the matching lines.

This will buffer only some short lines. The matching string(s) in the second sed. This should be quite low in resources used.

Or, somewhat more complex to understand, but the same idea in one sed:

a='ef be ad de'
hexdump -v -e '/1 "%02x "' infile.bin  |
    sed -u '/\n/P;//!s/'"$a"'/\n&\n/;D' |
        wc -l

With GNU grep's -P (perl-regexp) flag

LC_ALL=C grep -oaP '\xef\xbe\xad\xde' file | wc -l

LC_ALL=C is to avoid problems in multi-byte locales where grep would otherwise try to interpret sequences of bytes as characters.

-a treats binary files equivalent to text files (instead of the normal behavior, where grep only prints out whether there's at least one match or not)

PERLIO=:raw perl -nE '$c++ while m/\xef\xbe\xad\xde/g; END{say $c}' file

Which treats the input file(s) as binary (no translation for linefeeds or encodings, see perlrun) then loops over the input file(s) not printing incrementing a counter for all matches of the given hex (or whatever form, see perlre).