4 действительно 100 в двоичном формате, но ~4 - это не просто 011, это 11111...111011 с достаточным количеством ведущих 1 битов для заполнения представления типа в памяти.
В Python целые числа не имеют фиксированного размера, поэтому количество начальных 1 бит должно быть бесконечным. Хитрость заключается в том, чтобы использовать представление дополнения до двух для этих чисел и использовать эквивалентность: ~a <=> -a-1, поэтому ~4 фактически означает -5.