I thougth a hash might be faster, but no.

        Rate hash   if
hash  9329/s   -- -11%
if   10473/s  12%   --

        Rate hash   if
hash  9436/s   -- -11%
if   10599/s  12%   --

        Rate hash   if
hash  9341/s   -- -12%
if   10662/s  14%   --
[download]

Benchmark code:

use strict;
use warnings;

use Benchmark qw( cmpthese );

use constant INNER => $ARGV[0] || 10000;
use constant OUTER => $ARGV[1] || -3;

my $hash = <<'__EOI__';
   use strict;
   use warnings;
   my @x = our @data;
   my %c;
   while (@x) {
      my $i = shift(@x);
      my $j = shift(@x);
      ++$c{"$i$j"};
   }
__EOI__

my $if = <<'__EOI__';
   use strict;
   use warnings;
   my @x = our @data;
   my ($c00, $c01, $c10, $c11);
   while (@x) {
      my $i = shift(@x);
      my $j = shift(@x);
      if ($i) {
         if ($j) {
            $c11++;
         } else {
            $c10++;
         }
      } else {
         if ($j) {
            $c01++;
         } else {
            $c00++;
         }
      }
   }
__EOI__

our @data = map chr('' . int(rand(2))), 1..INNER;

cmpthese(OUTER, {
   'hash' => $hash,
   'if'   => $if,
});
[download]

A hash is definitely cleaner, though.

Cool... Guess I should've benchmarked my suggestion instead of just assuming it would be slower than the hash-based ideas.

Actually, unless I've severely mis-benchmarked it, it appears that my modest optimization (combined with blokhead's suggestion of using chop) even outdoes BrowserUK's bitwise version and still more so with fewer lines (based on BrowserUK's test code, I'm comparing every pair of lines):

100 lines/100 iterations:
          Rate bitwise  ifchop
bitwise 33.1/s      --    -41%
ifchop  56.5/s     71%      --

10 lines/10000 iterations:
          Rate bitwise  ifchop
bitwise 3226/s      --    -57%
ifchop  7463/s    131%      --

1000 lines/5 iterations:
        s/iter bitwise  ifchop
bitwise   3.06      --    -23%
ifchop    2.37     29%      --
[download]

(I actually suspect I'm doing something wrong in my test because I don't see why the number of lines would affect the relative performance at all. Update: I was doing something wrong. I forgot to pull the strings out of the array and was just comparing indexes in my version. With my version fixed to actually do the comparisons, the bitwise version is much faster, as I had initially expected:

          Rate  ifchop bitwise
ifchop  4.22/s      --    -87%
bitwise 33.3/s    690%      --
[download]

)

Benchmark code:

#!/usr/bin/perl -w
use strict;
use Benchmark qw(cmpthese);

our $S ||= 1;
our $B ||= 32;
our $N ||= 100;

srand( 1 );

our @strings = map {
    unpack 'b'. $B, rand( 2**32 )
} 1 .. $N;

my $bitwise = <<'EOBW';
our @strings;
my ($c00, $c01, $c10, $c11) = (0, 0, 0, 0);
for my $i ( 0 .. $#strings ) {
    for my $j ( $i+1 .. $#strings ) {
            $c00 = (  $strings[ $i ] |  $strings[ $j ] ) =~ tr[0][0];
            $c01 = ( ~$strings[ $i ] &  $strings[ $j ] ) =~ tr[\1][\1]
+;
            $c10 = (  $strings[ $i ] & ~$strings[ $j ] ) =~ tr[\1][\1]
+;
            $c11 = (  $strings[ $i ] &  $strings[ $j ] ) =~ tr[1][1];
    }
}
EOBW

my $ifchop = <<'EOIFC';
our @strings;
my ($c00, $c01, $c10, $c11) = (0, 0, 0, 0); 
for my $i ( 0 .. $#strings ) {
  for my $j ( $i+1 .. $#strings ) {
    # Need copies because chop is destructive
    # Oops... my $test_str_1 = $i;
    # my $test_str_2 = $j;
    my $test_str_1 = $strings[$i];
    my $test_str_2 = $strings[$j];

    while ($test_str_1) {
      my $x = chop $test_str_1;
      my $y = chop $test_str_2;
      if ($x) {
        if ($y) {
          $c11++;
        } else {
          $c10++;
        }
      } else {
        if ($y) {
          $c01++;
        } else {
          $c00++;
        }
      }
    }
  } 
}
EOIFC

cmpthese(100,
         { bitwise => $bitwise,
           ifchop  => $ifchop,
         });
[download]