I think you're being confused by the way you've represented decimal 41 in binary as 101001.
Remember that the leftmost binary digit of a signed integer represents the sign, 0 for positive, 1 for negative numbers. So you really need to fill out all the zeros to the left. To keep it simple, let's limit it to 8 bits. So 41 would really look like this in binary, 00101001. Since the leftmost digit is zero, this is a positive integer. (If you used 32 bits you'd of course just have a bunch more zeros to the left. If you actually had a 6-bit integer, 101001 would represent -23.)
The "negate" operator, ~, flips the bits so you get this 11010110. The leftmost digit is 1 so this is a negative integer. To figure out its decimal value, you just use the twos complement to find the positive value and add the minus sign. The twos complement is of course just the negation of the number plus 1, or 00101001 + 1 = 00101010, which is 42 in decimal, or -42 with the minus sign, since you know that 11010110 is negative.