arrays - Sum of bit differences among all pairs -

the problem statement following:

given integer array of n integers, find sum of bit differences in pairs can formed array elements. bit difference of pair (x, y) count of different bits @ same positions in binary representations of x , y. example, bit difference 2 , 7 2. binary representation of 2 010 , 7 111 ( first , last bits differ in 2 numbers).

examples:

input: arr[] = {1, 2} output: 4 pairs in array (1, 1), (1, 2)                        (2, 1), (2, 2) sum of bit differences = 0 + 2 +                          2 + 0                       = 4 

based on this post efficient (running time of o(n)) solution following:

the idea count differences @ individual bit positions. traverse 0 31 , count numbers i’th bit set. let count ‘count’. there “n-count” numbers i’th bit not set. count of differences @ i’th bit “count * (n-count) * 2″.

// c++ program compute sum of pairwise bit differences #include <bits/stdc++.h> using namespace std;  int sumbitdifferences(int arr[], int n) {     int ans = 0;  // initialize result      // traverse on bits     (int = 0; < 32; i++)     {         // count number of elements i'th bit set         int count = 0;         (int j = 0; j < n; j++)             if ( (arr[j] & (1 << i)) )                 count++;          // add "count * (n - count) * 2" answer         ans += (count * (n - count) * 2);     }      return ans; }  // driver prorgram int main() {     int arr[] = {1, 3, 5};     int n = sizeof arr / sizeof arr[0];     cout << sumbitdifferences(arr, n) << endl;     return 0; } 

what i'm not entirely clear on how running time linear when there 2 loops incrementing 1 each iteration. way i'm interpreting since outer loop iterating 0 32 (corresponding 0th , 32nd bits of each number) , because i'm guessing 32 bit shifts happen in same clock period (or relatively fast compared linear iteration), overall running time dominated linear iteration on array.

is correct interpretation?

in english, "my algorithm runs in o(n) time" translates "my algorithm runs in time @ proportional n large inputs". proportionality aspect of reason 32 iterations in outer loop don't make difference. execution time still proportional n.

let's @ different example:

for (int i=0; i<n; i++) {     (int j=0; j<n; j++) {         //     } } 

in example execution time proportional n² it's not o(n). o(n²). , technically o(n³) , o(n⁴), ... well. follows definition.

there's can talk stuff in english without misinterpretation, if want nail down concepts you're best off checking out formal definition in introductory algorithms textbook or online class , working out few examples.