Pixels in a GIF image do not express colours values directly, they are indexes in a palette.

Colours in a palette are completely unrelated to each other: you only have 256 palette entries in a common GIF so programs try to optimize it as much as possible.

Now, if you change a pixel value from, say, 23 (binary 00010111) to 22 (binary 00010110), inverting its low order bit, you get a different palette entry of course. Even if these entries are one next to the other, they may (and often will) point to completely unrelated colours. So colour number 23 can be an electric pink while colour 22 may be navy blue.

That's why steganography can hardly be applied to GIF images, and when a palette is involved, I think.

-- TMTOWTDI