minitest_xor_and_sum.md

Xor and Sum

You are given two positive integers a and b in binary representation. You should find the following sum modulo 10 ^ 9 + 7:

Summation(a xor (b shl i)) from i = 0 to 314159

where operation xor means exclusive OR operation, operation shl means binary shift to the left.

Please note, that we consider ideal model of binary integers. That is there is infinite number of bits in each number, and there are no disappearings (or cyclic shifts) of bits.

Input Format

The first line contains number a (1 ≤ a < 2105) in binary representation. The second line contains number b (1 ≤ b < 2105) in the same format. All the numbers do not contain leading zeros.

# input
11
1
# output
349822600

Output Format

Output a single integer − the required sum modulo 10 ^ 9 + 7.

Solution

For bit manipulation, we cn accumulate how many 1's appears in every position of the binary sequence.

assume we have input b: 110 then the left shift with n = 6 7 times would be like this (from right to left, low to high bits):

  ---------  
7        110
6       110
5      110
4     110
3    110
2   110
1  110
0 110
a 11
     bit 789 <-  (i - n) > 0   
 ---------- culmulaitve 1s  
 [22222210] count_b

Then for a given input a, the rule as follows:

If a's bit is 1 at index i, a will add more 1's (len + 1 - (b_count[i])) * pow_two[i]).
If a's bit is 0 at index i, a will add more 1's (b_count[i]) * pow_two[i].

For 0 to n,

i from 0 to (n + 1) + b.length
In position i  
  if bit is 1:
    sum = sum + ((n + 1 - counts) * pow_2[i])
  if bit is 0:
    sum = sum + (counts * pow_2[i])

Here counts is the array that calculate how many 1's appeared in that position:

int left = (i - n) < 0 ? 0 : (i - n);
int right = i >= b.length() ? b.length() - 1 : i;

//calculate range
long counts = count_b[right] - ( left == 0 ? 0 : count_b[left - 1]);

For left, i smaller than zero, just follow counts = count_b[right] For left, i larger than zero, then b_counts - (have not add 1's => b_counts[i - n - 1]). For right, i larger than b.length, set right to last index of b_counts.

Modulo Arithmatic

(a + c) mod b = ((a mod b) + (c mod b)) mod b
(a * c) mod b = ((a mod b) * (c mod b)) mod b

Java Integer range => 10 ^ 10, Long => 10 ^ 19.

Source code

// ...

// create 1's cumulation array.
for (int i = 0; i < count_b.length; i++) {
	count_b[i] = b.charAt(i) - '0';
	  if(i > 0)
			count_b[i] = count_b[i - 1] + count_b[i];
}

for (int i = 0; i < len + b.length(); i++) {
	int state = (i >= a.length()) ? 0 : a.charAt(i) - '0';
	int left = (i - len) < 0 ? 0 : (i - len);
	int right = i >= b.length() ? b.length() - 1 : i;

	//calculate range
	long range = count_b[right] - ( left == 0 ? 0 : count_b[left - 1]);

	if(state == 1)
		sum = (sum + ((len + 1 - range) * pow_two[i])) % modulo;
	else
		sum = (sum + (range * pow_two[i])) % modulo;
}

MiniTest

folder:
├── test
│   └── red_black_tree_rev_test.rb
└── red_black_tree_rev.rb

gem install minitest
ruby -I:test:. test/red_black_tree_rev_test.rb

require 'minitest/autorun'
require 'minitest/unit'
require 'red_black_tree_rev'

class RedBlackTreeTest < Minitest::Test
  def setup
    #initialize
  end
  
  def any_method_prepend_test()
    assert_equal target, value
  end
  
  def test_good; end
end