CODEWITHSUNDEEP
c++carraysalgorithmbitwise-operators
Kumar Vishal
Kumar Vishal

Reputation: 121

Cumulative BitWise OR on Char Array

I have a long char array size of 7K.

char arr[] = "1110010011....." ; // length 7K

I have to perform cumulative OR on array with window size of let say 3. That means:

arr[0] | arr[1] | arr[2] ;

arr[1] | arr[2] | arr[3] ;

what can be the best way can I do it less than O(n) or even if complexity is O(n) how can we make it faster?

Upvotes: 0

Views: 301

Answers (3)

Jim Mischel
Jim Mischel

Reputation: 134045

If you have an array of size N, which contains only 0's and 1's, and you want the result of ORing each K items (where K is the window size), all you have to do is keep track of where the last '1' is.

int last1 = -1;
int range_start = 0;
int range_end = window_size - 1;
for (int i = 0; i < array_size; ++i)
{
    if (a[i] == '1')
    {
        last1 = i;
    }
    if (i == range_end)
    {
        if (last1 >= range_start)
            // output 1
        else
            // output 0
    }
    ++range_start;
    ++range_end;
}

The idea here is that cumulative OR for any window size will be 1 if there is one or more 1's in the window. If the window contains all 0's, then the result is 0.

You might be able to optimize that a little bit by looking at the first window_size - 1 values in a separate loop, thereby eliminating the range_end variable, but it complicates your loop a little bit. I don't know if it'd be a net win.

Upvotes: 2

stgatilov
stgatilov

Reputation: 5533

If you repack your zero-one array into a bitset, then you can do it significantly faster. It would be about 32 times faster, but still take O(N) time. Also, you can use 64-bit words on 64-bit machine, then you'll get 64x improvement.

Note however, that for large N memory bandwidth would become the main bottleneck, so only 8x improvement would be achieved (because size is reduced in 8 times).

Here is the sample code:

int main() {
    char arr[] = "01000001011111000110010000011000111";
    int n = strlen(arr);

    //preparation: convert to bitset
    uint32_t bitset[sizeof(arr) / 32 + 3] = {0};
    for (int i = 0; i < n; i++)
      bitset[i/32] ^= (arr[i]=='1') << (i % 32);
    //solution: bit operations
    uint32_t result[sizeof(bitset) / sizeof(bitset[0])] = {0};
    for (int i = 0; i < (n + 31) / 32; i++) {
        uint32_t curr = bitset[i], next = bitset[i+1];
        result[i] = curr | (curr >> 1) | (next << 31) | (curr >> 2) | (next << 30);
    }

    printf("%s\n ", arr);
    for (int i = 0; i < n+2; i++)
        printf("%d", (result[i/32] >> (i%32)) & 1);
}

Update

The approach described above takes O(N W) time for variable window width W. For small W it is the fastest one, but it is not very efficient for large W.

Note that the problem can be solved in O(N) time for any window size. For example, you can precalculate prefix sums for your array of zeros/ones in O(N) time. Then for each window it is possible to determine the number of ones inside it in O(1) time as a difference of two sum values. As a result, you get a simple O(N) solution. It does not use any bitsets, and it is the fastest approach for really large W.

For intermediate window sizes (like W = 16), it is possible to modify the bitset-based approach to work in O(N log W) time, which may be faster than O(N W) version. The approach is somewhat similar to parallel reduction. Here is the sample code for W = 13:

for (int i = 0; i < (n + 31) / 32; i++) {
    uint64_t curr = *(uint64_t*)&bitset[i];
    curr |= (curr >> 1);
    curr |= (curr >> 2);
    curr |= (curr >> 4);
    curr |= (curr >> 5);
    result[i] = uint32_t(curr);
}

Upvotes: 3

Julian
Julian

Reputation: 424

To clarify, you'd like your output array to have n elements in it, each of which has the value of arr[n-1] | arr[n] | arr[n+1]. (with the possible exception of the first and the last elements, which don't have an arr[n-1] and arr[n+1] respectively.

If that's correct, then it is not possible to do this in less than O(n). You need to look at every element in the array at least once which alone takes O(n) time.

Fortunately, even the most naive approach meets that O(n) goal:

int size = strlen(arr);
char arr2[size];
for (int i=1; i<size-1; i++) { //ignore first and last element
    if (arr[i-1] == '1' || arr[i] == '1' || arr[i+2] == '1') {
        arr2[i] = '1';
    } else {
        arr2[i] = '0';
    }
}

At that point you have to decide what you mean by "efficient". You need to decide whether you want to reduce comparisons or assignments. Depending on your situation, either of these could be a valid choice and would result in very different solutions.

Upvotes: -3

Related Questions