Bitweiser Zugriff

[Der Martin]

Moin Daniel,

int bitreadshift(int i, int j) {
  return (i & (1 << j)) != 0;
}

wie ich schon Peter gegenüber angedeutet habe, geht es in den meisten Fällen, wo einzelne Bits abgefragt werden, nicht um die tatsächliche Wertigkeit des jeweiligen Bits; daher ist hier der Vergleich !=0 eigentlich sinnfrei (schadet aber auch nicht). Das Funktionsergebnis wird ja im realen Kontext sowieso auf "ungleich Null" abgefragt.

int bitreadarray(int i, int j) {
  return (i & array[j]) != 0;
}

Dito.

Vergessen:

long int time1 = clock() / (CLOCKS_PER_SEC / 1000.0);

for (int j = 0; j < count; ++j) {
    /* int k = 1 + (int) (31.0 * (rand() / (RAND_MAX + 1.0))); */
    for (int k = 0; k < 32; ++k) {
      x += bitreadshift(i, k);

Okay, hier kommt der numerische Wert doch zum Tragen, das ist aber eine untypische Anwendung für eine Bit-Abfrage.

Für die misstrauischen habe ich das auch mal disassembliert:

Und dann noch in einer so merkwürdigen Notation.  :-|

080483e0 <bitreadshift>:
80483e0:       55                      push   %ebp
80483e1:       89 e5                   mov    %esp,%ebp
80483e3:       8b 45 08                mov    0x8(%ebp),%eax
80483e6:       8b 4d 0c                mov    0xc(%ebp),%ecx
80483e9:       5d                      pop    %ebp
80483ea:       d3 f8                   sar    %cl,%eax
80483ec:       83 e0 01                and    $0x1,%eax
80483ef:       c3                      ret

Hier erkennt man aber, dass der Compiler den Ausdruck umformuliert hat. Was hier in Assembler wirklich formuliert wird, ist  "return ((i>>j) & 1)". Ich finde das bemerkenswert.

080483f0 <bitreadarray>:
80483f0:       55                      push   %ebp
80483f1:       89 e5                   mov    %esp,%ebp
80483f3:       8b 45 0c                mov    0xc(%ebp),%eax
80483f6:       8b 55 08                mov    0x8(%ebp),%edx
80483f9:       5d                      pop    %ebp
80483fa:       85 14 85 a0 97 04 08    test   %edx,0x80497a0(,%eax,4)
8048401:       0f 95 c0                setne  %al
8048404:       0f b6 c0                movzbl %al,%eax
8048407:       c3                      ret

Auffällig finde ich, dass da bei der Array-Variante anscheinend die AND-Operation wegoptimiert wird.

Keineswegs. Die test-Anweisung ist nämlich ein AND, bei dem das Ergebnis nicht gespeichert wird, gerade für solche Bit-Tests gedacht.

So long,
 Martin