Your cipher seems quite vulnerable to side-channels the way you describe it. Also, differential cryptanalysis depends mostly on a secure S-box. The steps you describe are superficial, since they don't effectively destroy patterns.
Assuming you're using an SP-network, which is generally what a 16-round block cipher would be, let's see what the steps are to perform encryption:
For each round, you
- Perform the nonlinear operation (S-box) on the plaintext
- mix the key with your intermediate ciphertext
- permutate the bits of your immediate ciphertext, providing diffusion
Your obstructing steps are:
- bitwise NOT (optional you make it ot not - randomly),
A bitwise NOT destroys no patterns and provides no nonlinearity
Deciding randomly whether to perform this operation only adds 1 bit per round, and makes side-channels that much more likely. This step is pretty much useless while adding potential for faulty implementation.
You should be mixing the round key anyway. I don't see how this is any different from a normal round cipher.
- moving bits by 0 to 127 places.
This could add 7 bits of security per round... maybe? but would be near-impossible to implement without allowing side-channel attacks. Data-dependent memory accesses are a really bad idea (I assume the amount you move the data would depend on the key, the plaintext, or some wacky logic based on both; this would immediately allow side-channels).
If, however, you mean to move the bits by some predefined amount, congratulations! You've implemented a P-box... Which you should be using anyway, considering you're making an SP-network.
If you want to resist differential cryptanalysis, the real solution is to design the nonlinear component (S-box) in a way that isn't vulnerable to differential cryptanalysis. Perhaps you could steal the S-box from AES since it's already well-understood?
Addendum: Make sure to defend against slide attacks! Your key cycle should be decently designed, as well, and side-channel attacks are horribly easy to accidentally allow in your implementation.