Counting number of perfect squares in an subarrays
Take random 64 bit integers. What are the chances that the AND of the first ten has more than one bit set? So for random numbers, I’d say the count is close to n^2 / 2, and it takes cn operations for small n to count them all. 

If $x=0$ or $x=4^k$ then x is a square, and x AND y is a square for any y. So if the AND of the first five numbers for example is one of these squares, then the AND of the first six, seven, eight, ..., n numbers is a square. Here's a simple algorithm:

total = 0
for 1 ≤ i ≤ n
    x = (all bits set)
    for i ≤ j ≤ n
        x = x AND a[j]
        if x = 0 or x = 4^k for some k
            total += n - j + 1
            break from for loop for j
        else if x is a square
            total += 1


This works well when the numbers are random. To improve for the worst case (for example alternating between 2 and 3, where this simple algorithm would take quadratic time), calculate the AND of groups of 2, 4, 8, 16, 32 etc. numbers, and observe that when calculating the AND of say a million 64 bit numbers, there will only be 64 different values. This is slightly complicated but not hard to implement if you are really interested in the solution.