loading...

Daily Challenge #255 - Is There an Odd Bit?

thepracticaldev profile image dev.to staff ・1 min read

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!

Discussion

pic
Editor guide
Collapse
vidit1999 profile image
Vidit Sarkar

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;
}
Collapse
mpixel profile image
Max Pixel

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.

Collapse
quoll profile image
Paula Gearon

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))))
Collapse
aminnairi profile image
Amin

Go

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)
        }
    }
}
Collapse
peter279k profile image
peter279k

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

Collapse
habisain profile image
Aleph Fell

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.

Collapse
bb4l profile image
bb4L

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
Collapse
anupa profile image
Anup Aglawe

Simple Python solution

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

print(any_odd(5))
Collapse
jpantunes profile image
JP Antunes

JS one liner

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