Oh, you might be right – I originally had that but second-guessed myself (thinking that once you have the k bit positions, you need to exhaustively search the 2^k possible settings for those bits). I guess for each possible set of positions you only need to check the case where they're all flipped.
Without the extra factor you need 6 flipped bits to reach a billion combinations (128 choose 6 is 5,423,611,200).
