Doppelte verschachtelte Schleife mit bitweiser Operation

  • Ich habe diese kleine Übung:

     for ( i = 0; i < 2 * n; i += 2 )
      for ( j = 1; j <= n; j <<= 1 )
        if ( j & i )
          foo ();
     

    (j <<= 1 bedeutet j = (j << 1), wobei << der bitweise Linksverschiebungsoperator ist. & ist der bitweise und Operator.)

    Ich soll bestimmen, wie oft foo -Funktion kann für einige n aufgerufen werden. Das Ergebnis sollte sowohl eine genaue Zahl (oder eine möglichst genaue Approximation) als auch eine asymptotische (wie O (n)) sein.

    23 September 2012
    GillesTimeless
1 answer
  • Die Anzahl der foo() -Aufrufe ist die Anzahl von 1 Bits in allen Zahlen von 0 bis $ n $ (oder allen geraden Zahlen zwischen $ 0 $ und $ 2n $ - dasselbe). Asymptotisch ist es $ O (n \ log n) $, da die Anzahl der 1 Bits um $ \ log_2 (n) / 2 $ liegt.

    Ich habe keine genaue Funktion. Es ist keine glatte Funktion - zum Beispiel $ f (1023) -f (1022) = 10 $, aber $ f (1024) -f (1023) = 1. $

    13 December 2012
    Mario