TL;DR
!(x >> k-1)
This is simple enough to be a viable answer that someone might come up with given one minute of time.
It only works within certain domains for x and k.
Coming up with a solution that covers the full integer domain, is a lot tougher.
The question lacks requirements, so I'll have to make a few assumptions.
For one, "a C condition with bitwise operator" could mean:
- at least one bitwise operator
- only bitwise operators (i.e. no other operators)
- as many bitwise operators as possible (i.e. as few other operators as possible)
Most answers seem to go for #1, and use a comparison operator (<) to do the actual 'less than' test.
Assuming this is an assignment to teach you about the binary representation of integer numbers,
comparison operators should be out of scope.
Not in the least because comparison with a power of two is a simple bit mask test.
For example, this works for k-1 = 8:
(x & ~0xFF) == 0
As demonstrated by other posters,
a bit shift operator can be used to dynamically construct the bit mask from k,
but it's actually a lot smarter to bit-shift x itself in the opposite direction.
Basically, we divide x by 2^(k-1).
If the (truncated) result is zero, then obviously, x is less than 2^(k-1).
(x >> k-1) == 0
or:
!(x >> k-1)
or (avoiding the arithmetic operator -):
!(x << 1 >> k)
or (avoiding the logical operator ! as well):
(~(x<<1 | x | x>>1 | x>>2 | x>>3 | ... | x>>31) >> k) & 1
The latter demands knowledge of the width (in bits) of type int; assuming 32 bits here.
All of the above work only within certain domains for both x and k.
- x must be non-negative; my expression will incorrectly return false for negative numbers.
- k must be non-negative, and less than the width (in bits) of
int (the type of x); my expression suffers from UB otherwise.
It is possible to make it work for wider domains.
I doubt it is on-topic for a one-minute assignment, but nevertheless it makes an interesting exercise.
To support negative x, just use INT_MIN as a bit mask to test the sign bit.
(x & INT_MIN) | ~((x<<1 | x | x>>1 | x>>2 | x>>3 | ... | x>>31) >> k) & 1
Or if you insist on always having 'true' represented by 1:
(x >> 31 | ~(x<<1 | x | x>>1 | x>>2 | x>>3 | ... | x>>31) >> k) & 1
(Again assuming 32 bits; if different, change the literal 31 accordingly.)
If k is negative, then every positive x should yield false.
Please note that this is identical to the behavior for zero k.
So just replace k with (k & ~k>>31) (the bitwise equivalent of (k < 0 ? 0 : k) in 32-bits architecture).
(x>>31 | ~(x<<1 | x | x>>1 | x>>2 | x>>3 | ... | x>>31) >> (k & ~k>>31)) & 1
For k greater than or equal to the size (in bits) of type int, every x should yield true:
(((k>>5 | k>>6 | k>>7 | ... | k>>30) & ~k>>31) | x>>31 | ~(x<<1 | x | x>>1 | x>>2 | x>>3 | ... | x>>31) >> (k & ~k>>31)) & 1
k>>5 as the first term may seem obscure. 5 is the logarithm of 32; in a 64-bits architecture we'd start with k>>6:
(((k>>6 | k>>7 | k>>8 | ... | k>>62) & ~k>>63) | x>>63 | ~(x<<1 | x | x>>1 | x>>2 | x>>3 | ... | x>>63) >> (k & ~k>>63)) & 1
If it would be acceptable to use not only bitwise, but also logical operators,
then the expression (here 32 bits) could be simplified to:
((k & ~31) && ~k>>31) || (x >> 31) || !(x << 1 >> (k & ~k>>31))
Here is a simple test (32 bits):
#include <stdio.h>
#include <limits.h>
static int purely_bitwise(int x, int k)
{
return (
((
k>>5 | k>>6 | k>>7 | k>>8 | k>>9 |
k>>10 | k>>11 | k>>12 | k>>13 | k>>14 | k>>15 | k>>16 | k>>17 | k>>18 | k>>19 |
k>>20 | k>>21 | k>>22 | k>>23 | k>>24 | k>>25 | k>>26 | k>>27 | k>>28 | k>>29 |
k>>30
) & ~k>>31) |
x>>31 |
~(
x<<1 | x | x>>1 | x>>2 | x>>3 | x>>4 | x>>5 | x>>6 | x>>7 | x>>8 | x>>9 |
x>>10 | x>>11 | x>>12 | x>>13 | x>>14 | x>>15 | x>>16 | x>>17 | x>>18 | x>>19 |
x>>20 | x>>21 | x>>22 | x>>23 | x>>24 | x>>25 | x>>26 | x>>27 | x>>28 | x>>29 |
x>>30 | x>>31
) >> (k & ~k>>31)
) & 1;
}
static int bitwise_and_logical(int x, int k)
{
return ((k & ~31) && ~k>>31) || (x >> 31) || !(x << 1 >> (k & ~k>>31));
}
static int comparison(int x, int k)
{
return k >= 32 || x < (k < 1 ? 1 : 1 << (k-1));
}
static int values[] = {
INT_MIN, INT_MIN+1, INT_MIN/2-1, INT_MIN/2, INT_MIN/2+1, -99, -9, -3, -2, -1,
0, 1, 2, 3, 9, 99, INT_MAX/2-1, INT_MAX/2, INT_MAX/2+1, INT_MAX-1, INT_MAX
};
#define LEN_VALUES (sizeof values / sizeof *values)
int main()
{
for (int ik = 0; ik < LEN_VALUES; ik++)
{
for (int ix = 0; ix < LEN_VALUES; ix++)
{
int x = values[ix];
int k = values[ik];
int actual1 = purely_bitwise(x, k);
int actual2 = bitwise_and_logical(x, k);
int expected = comparison(x, k);
if (actual1 != expected || actual2 != expected)
{
printf("x = %11d, k = %11d: expected = %d, actual = %d, %d\n",
x, k, expected, actual1, actual2);
}
}
}
return 0;
}
The program outputs nothing, which is good, as every line of output would be a failed test case.
