Check Leap Year - without using division operation

Question

How to check if the given year is a leap year, without using division operation or some library method in Java. Is it possible to check this using a bitwise operator?

PS: validation not necessary for centuries

Does the modulo operator (`%`) count as an option? And just out of curiosity, why is division not an option? — n247s, Sep 04 '18 at 04:04
@n247s Likely a homework challenge for a student. Otherwise, the simple solution would be: `java.time.Year.isLeap( 2018 )` — Basil Bourque, Sep 04 '18 at 04:05
Can you just put in the question whether you have to check for centuries? — billjamesdev, Sep 06 '18 at 05:01
`return ((year & 3) == 0;` To check century years you need modulo (which is a division operation): `return ((year & 3) == 0 && ((year % 25) != 0 || (year & 15) == 0));` More at: https://stackoverflow.com/a/11595914/733805 — Kevin P. Rice, Dec 10 '18 at 11:23

score 3 · Accepted Answer · edited Sep 04 '18 at 05:20

Here are some ways of identifying leap years without using a modulo function.

Firstly, let’s assume (or test) that the year is in the range 1901 - 2099.

A leap year expressed as a binary number will have 00 as the last two digits. So:

it’s a leap year if year & (not 4) == 0
If you have a function available to truncate a real number to an integer then this works:

x = trunc(year / 4)

it’s a leap year if x * 4 == year
If you have shift (not circular shift) operators, which I’m sure Verilog has then:

x = year >> 2

it’s a leap year if (x << 2) == year

If the assumption about the range being 1901 - 2099 is false then you’ll need some extra logic to eliminate 1900, 1800, 1700 and 2100, 2200, 2300 and so on.

billjamesdev · Answer 2 · 2018-10-29T21:16:59.593

2

Well, sure. Since division or mod by powers of 2 (in this case, 4), is just a bit check.

boolean isLeapYear( int year ) {
    return (( year & 3 ) == 0 );  // if the bottom two bits are 0, then the int is divisible by 4
}

Note this isn't perfect, as some centuries aren't leap years, but it seems that's not relevant to your question (as you now state).

edited Oct 29 '18 at 21:16

answered Sep 04 '18 at 04:03

billjamesdev

14,554
6
53
76

score 1 · Answer 3 · answered Sep 04 '18 at 10:24

If a year is a century year, meaning divisible by 100, then it needs to be divisible by 400 to be called as a leap year.
If a year is not a century year, then it needs to be divisible by 4 to be called as a leap year.

Below Code uses binary search to check if a number is divisible by another number or not(since / is not allowed, I am not sure if you could use % though).

    public static boolean isLeapYear(int year){
        return isDivisible(1,year,100,year) ? isDivisible(1,year,400,year) : isDivisible(1,year,4,year);
    }

    private static boolean isDivisible(int low,int high,int divisor,int dividend){
        int mid = 0;
        while(low <= high){
            mid = low + ((high - low) >> 1);
            int result = divisor * mid;
            if(result == dividend) return true;
            else if(result > dividend) high = mid - 1;
            else low = mid + 1;
        }

        return false;
    }

score 0 · Answer 4 · answered Sep 04 '18 at 08:54

0

Yes, you can do it without using any arithmetic operations. Use a Map which maps from year to a boolean - whether the year is a leap year or no.

answered Sep 04 '18 at 08:54

Teodor Dyakov

344
2
13

So, individually add values to map? – nice_dev Sep 04 '18 at 10:25

score 0 · Answer 5 · answered Oct 29 '18 at 21:21

0

Year.isLeap(someYear)

You should be more specific with your requirements, this is a site for programmers :)

answered Oct 29 '18 at 21:21

Michael

41,989
11
82
128

Check Leap Year - without using division operation

5 Answers5