Optimize array summation (subset issue)

In the hottest part of my program (90% of the time in gprof), I need to sum one array A to another B. Both arrays are 2 ^ n in size (n is 18..24) and contain an integer (for simplicity, the actually stored element is mpz_t or a small array of int). Summing rule: for each i'm at 0..2 ^ n-1, set B[i] = sum (A[j])where jis the bit vector, and j & ~ i == 0(in other words, the k-th bit of any jcan't be set to 1 if the k-th bit is inot equal to 1) .

My current code (this is the body of the inner loop itself) does this in a time of 2 ^ (1,5 * n) sums, since I will iterate for each (on average) 2 ^ (n / 2) elements from A.

  int A[1<<n]; // have some data
  int B[1<<n]; // empty
  for (int i = 0; i < (1<<n); i++ ) {
    /* Iterate over subsets */
    for (int j = i; ; j=(j-1) & i ) {
      B[i] += A[j];  /* it is an `sum`, actually it can be a mpz_add here */
      if(j==0) break;
    }
  }

My mentioned that almost any amount is recalculated from the values ​​summarized earlier. I suggest there may be code that does the same task in n* 2^nsums time .

My first idea B[i] = B[i_without_the_most_significant_bit] + A[j_new]; where j_new is just j having the most significant bit of i in state "1". This reduces my time, but it’s not enough (still hours and days according to the actual size of the problem):

  int A[1<<n];
  int B[1<<n];
  B[0] = A[0]; // the i==0 will not work with my idea and clz()
  for (int i = 1; i < (1<<n); i++ ) {
    int msb_of_i = 1<< ((sizeof(int)*8)-__builtin_clz(i)-1);
    int i_wo_msb = i & ~ msb;
    B[i] = B[i_wo_msb];
    /* Iterate over subsets */
    for (int j_new = i; ; j_new=(j_new-1) & i ) {
      B[i] += A[j_new];  
      if(j_new==msb) break; // stop, when we will try to unset msb
    }
  }

Can you suggest a better algorithm?

Additional image, a list of i and j, summarized for each i for n = 4:

i  j`s summed
0  0
1  0 1
2  0 2
3  0 1 2 3
4  0 4
5  0 1 4 5
6  0 2 4 6
7  0 1 2 3 4 5 6 7
8  0                8
9  0 1              8 9
a  0 2              8 a
b  0 1 2 3          8 9 a b
c  0 4              8 c
d  0 1 4 5          8 9 c d
e  0 2 4 6          8 a c e
f  0 1 2 3 4 5 6 7  8 9 a b c d e f

Note the similarity of the figures.

PS msb magic from here: Undo the most significant bit in a word (int32) [C]