Here is an O(N) algorithm:
Traverse the bits from left to right. Each additional position is equivalent to multiplying the current value by 2, and then adding either 0 or 1. This is also true in modulo-13 arithmetic. When you get to the last bit, see if the final value is equal to 0. If it is, then the original number was divisible by 13.