dev.to staff

Posted on Jun 9, 2020

Daily Challenge #255 - Is There an Odd Bit?

#challenge

Convert a given integer to binary. Return 1 when ANY odd bit of x equals 1; 0 otherwise.

Examples
any_odd(2) will return 1 because at least one odd bit is 1 (0010).
any_odd(170) will return 1 because all of the odd bits are 1 (10101010).

Tests
any_odd(5)
any_odd(7)
any_odd(10)

Good luck!

This challenge comes from mtruong1999 on CodeWars. Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge idea for a future post? Email yo+challenge@dev.to with your suggestions!

Top comments (9)

Vidit Sarkar • Jun 9 '20 • Edited

Here is a C++ solution, (considering given number is positive and 32-bit integer)

#include <bits/stdc++.h>
using namespace std;

int any_odd(unsigned int number){
    return (number & 0xAAAAAAAA) != 0; // 0xAAAAAAAA has all its odd bits set, so if result is not 0 then number has at least one odd set bit
}

int main(){
    cout << any_odd(2) << "\n"; // output -> 1
    cout << any_odd(170) << "\n"; // output -> 1
    cout << any_odd(5) << "\n"; // output -> 0
    cout << any_odd(7) << "\n"; // output -> 1
    cout << any_odd(10) << "\n"; // output -> 1
    cout << any_odd(0) << "\n"; // output -> 0
    return 0;
}

Max Pixel • Jun 9 '20 • Edited

This C++ solution supports a number of any size (byte, 16-bit, 32-bit, etc), and compiles down to just a single CPU instruction for every invocation of any_odd.

constexpr unsigned long long odd_bits{0b1010101010101010101010101010101010101010101010101010101010101010ull};
template<typename T>
inline bool any_odd(const T& test)
{
    static_assert(std::is_integral<T>::value, "any_odd only works with integers");
    return (*reinterpret_cast<const T*>(&odd_bits) & test) != 0;
}

Note that without the reinterpret_cast, an unnecessary cdqe instruction will likely be introduced, even with maximum optimization turned on.

Paula Gearon • Jun 9 '20

Since all integers and longs are signed in the JVM, this makes the high order bit awkward to work with in Clojure. Unlike Java, all integral numbers are assumed to be long, so there is no special syntax to indicate this. And when numbers get large enough, they automatically roll over into BigInt values.

Consequently, even though Java can say:

jshell> 0xAAAAAAAAAAAAAAAAL
$1 ==> -1

Clojure does not have this option of indicating that number is a long (and hence negative because of the most significant bit):

user=> 0xAAAAAAAAAAAAAAAA
12297829382473034410N

(Note: the N indicates a BigInt value)

So we need to use the 2s complement form, and negate the value:

(defn any-odd [x] (not (zero? (bit-and -0x5555555555555556 x))))

Aleph Fell • Jun 9 '20

Simple Python solution, exploiting that any_even has a nice recursive case.

def any_even(x):
   if x == 0: return False
   elif x % 2: return True
   else: return any_even(x >> 2)
def any_odd(x): return any_even(x >> 1)

Note that if you know the size of an integer you could do this with bitmasking, so languages like C have much more efficient (and somewhat less interesting) solutions. Languages with unbounded ints (like Python) obviously can't do this.

peter279k • Jun 20 '20

Here is my solution with Python:

def any_odd(x):
    print(x)
    bin_string = ""

    num = x
    while num != 0:
        bit = num % 2
        num = int(num / 2)

        bin_string = str(bit) + bin_string

    index = len(bin_string) - 1

    for bit in bin_string:
        if index % 2 == 1 and bit == '1':
            return 1
        index -= 1

    return 0

Amin • Jun 9 '20

package odd

func AnyOdd(number uint) uint8  {
    for index := 0; number != 0; index, number = index + 1, number / 2 {
        if index % 2 != 0 && number % 2 == 1 {
            return 1
        }
    }

    return 0
}

Tests

package odd_test

import (
    "testing"
    "github.com/aminnairi/odd"
)

func TestOnes(t *testing.T) {
    var expectation uint8 = 1

    ones := []uint{170, 2, 7, 10}

    for _, value := range ones {
        result := odd.AnyOdd(value)

        if result != expectation {
            t.Errorf("oddAnyOdd(%d) should be %d, %d received", value, expectation, result)
        }
    }
}

func TestZeros(t *testing.T) {
    var expectation uint8 = 0

    zeros := []uint{5, 21, 85, 341}

    for _, value := range zeros {
        result := odd.AnyOdd(value)

        if result != expectation {
            t.Errorf("oddAnyOdd(%d) should be %d, %d received", value, expectation, result)
        }
    }
}

bb4L • Jun 9 '20

Solution in nim:

import strutils

proc anyOdd*(data: BiggestInt): int =
for i, c in $(toBin(data, 15)):
        if c == '1' and i mod 2 == 1:
            return 1
    return 0

Anup Aglawe • Jun 10 '20 • Edited

Simple Python solution

def any_odd(num): // 45812984490 = b(1010101....10)
  return 0 if ((45812984490 & num) == 0) else 1

print(any_odd(5))

JP Antunes • Jun 10 '20 • Edited

JS one liner

const isOdd = (num, i = 1) => num >= 1 ? (i % 2 == 1 && parseInt(num / 2) % 2 == 1) : isOdd(parseInt((num / 2), i++))

DEV Community

Daily Challenge #255 - Is There an Odd Bit?

Top comments (9)

Read next

AIM Weekly for 04Nov2024

End to End Data Engineering OTP Pipeline Project

Building a Regex Engine in Go: Introducing MatchGo

Total Quality Management Framework with AI: Revolutionizing Business Excellence