title: Constrained counting sets on binary codes
body: <p>Problem formulation: Given a binary code of length l, for every t bits set (l%t=0), if there exists at least one bit of value 1, we add 1 to the result.</p>
  
  <p>My question : How to efficiently get the final result?</p>
  
  <p>For example, we have a binary code <code>010 110 000</code>, and t=3. Then the final result is 2. Since for <code>000</code>, there is no bit of value 1. For 110, there exists at least one bit of value 1. We add 1 to the result. For 010, there also exists one bit of value 1. We add 1 to the result. Thus, the final result is 2.</p>
  
  <p>My question is that how to efficiently solve this problem without scanning through every t bits, which causes a time complexity linear with the length of the binary code.</p>
  
  <p>For the counting set problem (calculate how many 1's in a binary code), there are some algorithms which take constant time to solve it by taking a limited number of mask and shift operations such as the <a href="https://blogs.msdn.microsoft.com/jeuge/2005/06/08/bit-fiddling-3/" rel="nofollow noreferrer">MIT HAKMEM Count</a> algorithm.</p>
  
  <p>However, existing algorithms for the traditional counting set problem cannot be used to solve my problem. </p>
  
  <p>Does anyone know some tricks for my problems? You can assume a maximum length of the input binary code if it makes the problem easier to solve.</p>