How to Perform a Pairwise Binary Operation Between the Elements of Two Containers

How do I perform a pairwise binary operation between the elements of two containers?

A lambda should do the trick:

#include <algorithm>
#include <iterator>

std::transform(a.begin(), a.end(),     // first
               b.begin(),              // second
               std::back_inserter(c),  // output
               [](uint32_t n, uint32_t m) { return n & m; } );

Even better, thanks to @Pavel and entirely C++98:

#include <functional>

std::transform(a.begin(), a.end(), b.begin(),
               std::back_inserter(c), std::bit_and<uint32_t>());

Sum two vector and store stl algorithm

You can use std:::transform

std::transform(v1.begin(), v1.end(), v2.begin(), v2.begin(), std::plus<>());

Sum values of 2 vectors

You can use std::transform and std::plus<int>()

std::vector<int> a;//looks like this: 2,0,1,5,0
std::vector<int> b;//looks like this: 0,0,1,3,5

// std::plus adds together its two arguments:
std::transform (a.begin(), a.end(), b.begin(), a.begin(), std::plus<int>());
// a = 2,0,2,8,5

This form of std::transform takes 5 arguments:

Two first are input iterators to the initial and final positions of the first sequence.
The third is an input iterator to the initial position of the second range.
The fourth is an output iterator of the initial position of the range where the operation results are stored.
The last argument is a binary function that accepts two elements as argument (one of each of the two sequences), and returns some result value convertible to the type pointed by OutputIterator.

Vector addition operation

This line doesn't work, because there's no v3[i] allocated:

v3[i] = v1[i] + v2[i];

You have two choices, either use 'push_back'

v3.push_back( v1[i] + v2[i] );

Or resize the array to the given size before hand:

v3.resize( v1.size() );

If you push_back, it will be nice to preallocate the space anyway:

v3.reserve( v1.size() );

And finally, you can try to read up on std::valarray instead, as those operations are already built into it!

Edit: and yes, as Johannes noted, you have a problem with floating point division :>

Algorithm to merge (fuse two items together, replace them with the fusion) items in std::list (i.e. destructive clustering)

Following is what I ended up with.

It's ragged: pairs are not compared twice (0,1 and 1,0)

instances are not compared to themselves (0,0)

#include <iostream>
#include <list>
#include <cmath>
#include <algorithm>
using namespace std;

class percepUnit {
    public:
        int cx, cy; // location of percept in frame
        bool remove; // used to delete percepts

        // constructor method
        percepUnit(int ix, int iy) {
            cx = ix;
            cy = iy;
            remove = false;
        }
};

bool canMerge(percepUnit unitA, percepUnit unitB) {

    double dist = sqrt(pow(abs(unitA.cx-unitB.cx),2)+ pow(abs(unitA.cy-unitB.cy),2));
    return (dist < 3);
}

percepUnit merge(percepUnit unitA, percepUnit unitB) {
    int x,y;

    x = unitA.cx+unitB.cx/2;
    y = unitA.cy+unitB.cy/2;

    return (percepUnit(x,y));
}

// Predicate to use remove_if to delete merge inputs.
bool removePercepsMarkedForRemoval(const percepUnit &unit) {
    return unit.remove;
}

int main() {
    list<percepUnit> mylist;
    list<percepUnit> mergedlist;
    list<percepUnit>::iterator mylistiterOutter;
    list<percepUnit>::iterator mylistiterInner;

    mylist.push_back(percepUnit(0,0));
    mylist.push_back(percepUnit(2,2));

    mylist.push_back(percepUnit(5,5));
    mylist.push_back(percepUnit(7,7));

    mylist.push_back(percepUnit(15,15));

    for(mylistiterOutter = mylist.begin(); mylistiterOutter != mylist.end(); mylistiterOutter++) {

        mylistiterInner = mylistiterOutter; // bypass the same pair twice

        while (mylistiterInner != mylist.end()) {
            if (canMerge(*mylistiterOutter, *mylistiterInner) and mylistiterOutter != mylistiterInner) { // bypass the same instance
                mergedlist.push_back(merge(*mylistiterOutter, *mylistiterInner));
                mylistiterOutter->remove = true;
                mylistiterInner->remove = true;
            }
            mylistiterInner++;
        }
    }

    mylist.erase(remove_if(mylist.begin(), mylist.end(), removePercepsMarkedForRemoval), mylist.end());

    mylist.splice(mylist.end(), mergedlist);

    return(0);
}

Python AND operator on two boolean lists - how?

and simply returns either the first or the second operand, based on their truth value. If the first operand is considered false, it is returned, otherwise the other operand is returned.

Lists are considered true when not empty, so both lists are considered true. Their contents don't play a role here.

Because both lists are not empty, x and y simply returns the second list object; only if x was empty would it be returned instead:

>>> [True, False] and ['foo', 'bar']
['foo', 'bar']
>>> [] and ['foo', 'bar']
[]

See the Truth value testing section in the Python documentation:

Any object can be tested for truth value, for use in an if or while condition or as operand of the Boolean operations below. The following values are considered false:

[...]

any empty sequence, for example, '', (), [].

[...]

All other values are considered true — so objects of many types are always true.

(emphasis mine), and the Boolean operations section right below that:

x and y
if x is false, then x, else y

This is a short-circuit operator, so it only evaluates the second argument if the first one is True.

You indeed need to test the values contained in the lists explicitly. You can do so with a list comprehension, as you discovered. You can rewrite it with the zip() function to pair up the values:

[a and b for a, b in zip(x, y)]

Count the Subarray's which has bitwise and of its elements equal to Zero

You can do this in O(n) time using a sliding window.

If we know that a subarray of A on indices [L, R] has an & of zero, then we know that all larger subarrays ([L, R + 1], [L, R + 2], [L, R + 3], ...) will also have an & of zero due to monotonicity of & under inclusion.

For example, computing the partial & products of an array from the left:

Array (Base 10): [  7,  3,   10,   5]

Array (Binary) : [111, 11, 1010, 101]

Partial &s     : [111, 11,   10,   0]

We'll iterate over the right end of our sliding window, while storing the smallest left end (i.e. the largest window) such that A[left, left + 1, ... right] has a nonzero bitwise &. Note that this left end can only ever increase as the right end increases.

To update our window, we'll need to

Be able to take an & of our window with A[right] (easy)
Be able to remove the & of A[left] from our window (hard)

To do removals efficiently, we'll instead track the count of set-bits for all elements in our window at each bit position. This lets us add and remove elements from our window, and test whether the & of our window is zero by testing whether each set bit position has a count less than the length of the window.

Here's a walkthrough of the maximal nonzero windows on an example array:

Base 10:
A = [7, 2, 9, 8, 6, 12, 109, 28, 14, 19]

Binary:
111, 10, 1001, 1000, 110, 1100, 1101101, 11100, 1110, 10011

Maximal nonzero [windows] at each right endpoint:

--------------------------------------------------------------
[111], 10, 1001, 1000, 110, 1100, 1101101, 11100, 1110, 10011
^   ^

left = 0, right = 0, size = 1

--------------------------------------------------------------
[111, 10], 1001, 1000, 110, 1100, 1101101, 11100, 1110, 10011
^       ^

left = 0, right = 1, size = 2

--------------------------------------------------------------
111, 10, [1001], 1000, 110, 1100, 1101101, 11100, 1110, 10011
         ^    ^                                         

left = 2, right = 2, size = 1

--------------------------------------------------------------
111, 10, [1001, 1000], 110, 1100, 1101101, 11100, 1110, 10011
         ^          ^                                         

left = 2, right = 3, size = 2

--------------------------------------------------------------
111, 10, 1001, 1000, [110], 1100, 1101101, 11100, 1110, 10011
                     ^   ^

left = 4, right = 4, size = 1

--------------------------------------------------------------
111, 10, 1001, 1000, [110, 1100], 1101101, 11100, 1110, 10011
                     ^         ^

left = 4, right = 5, size = 2

--------------------------------------------------------------
111, 10, 1001, 1000, [110, 1100, 1101101], 11100, 1110, 10011
                     ^                  ^

left = 4, right = 6, size = 3

--------------------------------------------------------------
111, 10, 1001, 1000, [110, 1100, 1101101, 11100], 1110, 10011
                     ^                         ^

left = 4, right = 7, size = 4

--------------------------------------------------------------
111, 10, 1001, 1000, [110, 1100, 1101101, 11100, 1110], 10011
                     ^                               ^   

left = 4, right = 8, size = 5

--------------------------------------------------------------
111, 10, 1001, 1000, 110, 1100, 1101101, 11100, [1110, 10011]
                                                ^           ^   

left = 8, right = 9, size = 2

Here, the sum of nonzero-& window sizes is 23. As a length 10 array has 55 possible subarrays, the answer is 55 - 23 = 32 bitwise-&-zero subarrays.

Python code:

def count_bitwise_and_zero(nums: List[int]) -> int:
    """Count nonempty subarrays with & of elements equal to 0.
    Given a list on nonnegative integers,
    returns the number of contiguous, nonempty subarrays for which the
    bitwise and of all elements in the subarray are equal to 0.

    Runs in linear time on fixed-width integers.
    """

    def get_set_bit_indices(x: int) -> List[int]:
        """Return indices of set bits in x"""
        pow_2 = 1
        exponent = 0
        set_bits = []

        while pow_2 <= x:
            if pow_2 & x != 0:
                set_bits.append(exponent)

            exponent += 1
            pow_2 *= 2

        return set_bits

    def is_bitwise_and_zero(window_length: int, bit_counts: Dict[int, int]) -> bool:
        """Given bit counts for a window of an array, return whether the
        window's elements have bitwise AND equal to zero."""
        return all(value < window_length for value in bit_counts.values())

    n = len(nums)
    total_subarray_count = n * (n + 1) // 2

    nonzero_subarray_count = 0
    window_bit_counts = Counter()

    """At every iteration start, [left_idx, right_idx] is the longest subarray
    ending at right_idx whose bitwise AND is nonzero."""
    left_idx = 0

    for right_idx, right_element in enumerate(nums):
        if right_element == 0:
            window_bit_counts.clear()
            left_idx = right_idx + 1
            continue

        # Expand window to include right
        window_bit_counts += Counter(get_set_bit_indices(right_element))

        # Shrink window until AND is nonzero
        while (left_idx < right_idx
               and is_bitwise_and_zero(right_idx - left_idx + 1, window_bit_counts)):

            window_bit_counts -= Counter(get_set_bit_indices(nums[left_idx]))
            left_idx += 1

        nonzero_subarray_count += (right_idx - left_idx + 1)

    return total_subarray_count - nonzero_subarray_count

Example usage:

count_bitwise_and_zero([7, 2, 9, 8, 6, 12, 109, 28, 14, 19])
>>> 32

N.B. There's an assumption that the maximum bit-width of the integers is constant. To get a linear-time solution when integers can be arbitrarily large, you'll need to keep a meta-counter, which tracks counts of counts of set bits.

As an exercise, you can try to generalize to the problem of bitwise & equal to some target t which may be greater than zero; it takes a bit more work.

optimise binary_fold algorithm and make it left (or right) associative

I have two TMP versions. Which one is better, depends on the data types, I guess:

Solution A:

First, let's find a good offset for the split point (powers of two seem great):

template<std::ptrdiff_t diff, std::ptrdiff_t V = 2>
struct offset
{
  static constexpr std::ptrdiff_t value =
      (V * 2 < diff - 1) ? offset<diff, V * 2>::value : V;
};

// End recursion
template<std::ptrdiff_t diff>
struct offset<diff, 1<<16>
{
  static constexpr std::ptrdiff_t value = 1<<16;
};

// Some special cases
template<> 
struct offset<0, 2>
{
  static constexpr std::ptrdiff_t value = 0;
};

template<>
struct offset<1, 2> 
{
  static constexpr std::ptrdiff_t value = 0;
};

template<>
struct offset<2, 2>
{
  static constexpr std::ptrdiff_t value = 0;
};

With this, we can create a recursive TMP version:

template <std::ptrdiff_t diff, class It, class Func>
auto binary_fold_tmp(It begin, It end, Func op)
    -> decltype(op(*begin, *end))
{
  assert(end - begin == diff);
  switch (diff)
  {
    case 0:
      assert(false);
      return 0;  // This will never happen
    case 1:
      return *begin;
    case 2:
      return op(*begin, *(begin + 1));
    default:
    {  // first round to the nearest multiple of 2 and then advance
      It mid{begin};
      std::advance(mid, offset<diff>::value);
      auto left = binary_fold_tmp<offset<diff>::value>(begin, mid, op);
      auto right =
          binary_fold_tmp<diff - offset<diff>::value>(mid, end, op);
      return op(left, right);
    }
  }
}

This can be combined with a non-TMP version like this, for instance:

template <class It, class Func>
auto binary_fold(It begin, It end, Func op)
    -> decltype(op(*begin, *end))
{
  const auto diff = end - begin;
  assert(diff > 0);
  switch (diff)
  {
    case 1:
      return binary_fold_tmp<1>(begin, end, op);
    case 2:
      return binary_fold_tmp<2>(begin, end, op);
    case 3:
      return binary_fold_tmp<3>(begin, end, op);
    case 4:
      return binary_fold_tmp<4>(begin, end, op);
    case 5:
      return binary_fold_tmp<5>(begin, end, op);
    case 6:
      return binary_fold_tmp<6>(begin, end, op);
    case 7:
      return binary_fold_tmp<7>(begin, end, op);
    case 8:
      return binary_fold_tmp<8>(begin, end, op);
    default:
      if (diff < 16)
        return op(binary_fold_tmp<8>(begin, begin + 8, op),
                  binary_fold(begin + 8, end, op));
      else if (diff < 32)
        return op(binary_fold_tmp<16>(begin, begin + 16, op),
                  binary_fold(begin + 16, end, op));
      else
        return op(binary_fold_tmp<32>(begin, begin + 32, op),
                  binary_fold(begin + 32, end, op));
  }
}

Solution B:

This calculates the pair-wise results, stores them in a buffer, and then calls itself with the buffer:

template <std::ptrdiff_t diff, class It, class Func, size_t... Is>
auto binary_fold_pairs_impl(It begin,
                            It end,
                            Func op,
                            const std::index_sequence<Is...>&)
    -> decltype(op(*begin, *end))
{
  std::decay_t<decltype(*begin)> pairs[diff / 2] = {
      op(*(begin + 2 * Is), *(begin + 2 * Is + 1))...};

  if (diff == 2)
    return pairs[0];
  else
    return binary_fold_pairs_impl<diff / 2>(
        &pairs[0],
        &pairs[0] + diff / 2,
        op,
        std::make_index_sequence<diff / 4>{});
}

template <std::ptrdiff_t diff, class It, class Func>
auto binary_fold_pairs(It begin, It end, Func op) -> decltype(op(*begin, *end))
{
  return binary_fold_pairs_impl<diff>(
      begin, end, op, std::make_index_sequence<diff / 2>{});
}

This template function requires diff to be a power of 2. But of course you can combine it with a non-template version, again:

template <class It, class Func>
auto binary_fold_mix(It begin, It end, Func op) -> decltype(op(*begin, *end))
{
  const auto diff = end - begin;
  assert(diff > 0);
  switch (diff)
  {
    case 1:
      return *begin;
    case 2:
      return binary_fold_pairs<2>(begin, end, op);
    case 3:
      return op(binary_fold_pairs<2>(begin, begin + 1, op),
                *(begin + (diff - 1)));
    case 4:
      return binary_fold_pairs<4>(begin, end, op);
    case 5:
      return op(binary_fold_pairs<4>(begin, begin + 4, op),
                *(begin + (diff - 1)));
    case 6:
      return op(binary_fold_pairs<4>(begin, begin + 4, op),
                binary_fold_pairs<4>(begin + 4, begin + 6, op));
    case 7:
      return op(binary_fold_pairs<4>(begin, begin + 4, op),
                binary_fold_mix(begin + 4, begin + 7, op));
    case 8:
      return binary_fold_pairs<8>(begin, end, op);
    default:
      if (diff <= 16)
        return op(binary_fold_pairs<8>(begin, begin + 8, op),
                  binary_fold_mix(begin + 8, end, op));
      else if (diff <= 32)
        return op(binary_fold_pairs<16>(begin, begin + 16, op),
                  binary_fold_mix(begin + 16, end, op));
      else
        return op(binary_fold_pairs<32>(begin, begin + 32, op),
                  binary_fold_mix(begin + 32, end, op));
  }
}

I measured with the same program as MtRoad. On my machine, the differences are not as big as MtRoad reported. With -O3 solutions A and B seem to be slightly faster than MtRoad's version, but in reality, you need to test with your types and data.

Remark: I did not test my versions too rigorously.