## Sunday, November 13, 2016

### Multiples of 4 (An Interesting Method) - GeeksforGeeks

Multiples of 4 (An Interesting Method) - GeeksforGeeks
Given a number n, the task is to check whether this number is a multiple of 4 or not without using +, -, * ,/ and % operators.

An interesting fact for n > 1 is, we do XOR of all numbers from 1 to n and if the result is equal to n, then n is a multiple of 4 else not.
`// Returns true if n is a multiple of 4.`
`bool` `isMultipleOf4(``int` `n)`
`{`
`    ``if` `(n == 1)`
`       ``return` `false``;`

`    ``// Find XOR of all numbers from 1 to n`
`    ``int` `XOR = 0;`
`    ``for` `(``int` `i = 1; i <= n; i++)`
`        ``XOR = XOR ^ i;`

`    ``// If XOR is equal n, then return true`
`    ``return` `(XOR == n);`
`}`

The idea is to remove last bits using >>, then multiply with 4 using <<. If final result is same as n, then last two bits were 0, hence number was a multiple of four.
`bool` `isMultipleOf4(``long` `long` `n)`
`{`
`    ``if` `(n==0)`
`        ``return` `true``;`

`    ``return` `(((n>>2)<<2) == n);`
`}`