6
\$\begingroup\$

Write the shortest code to find the remainder when an input number N is divided by 2^M. You cannot use /,* and % operator.

Input Specification
Number of test cases followed by a pair of integers on each line.

Sample Input
1
150 6

Sample Output
22

Limits
1<T<1000
1<N<2^31
1<B<31

Time Limit
1 Sec
\$\endgroup\$
2
\$\begingroup\$

Golfscript - 16 chars

~]1>2/{~2\?(&n}/

For a single pair or numbers this would sufficient

~2\?(&

By the way, the / does not stand for division here :)

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$
scanf("%d", &T);
while(T--){
   scanf("%d,%d", &N,&M);
   printf("%d",N&~(~0 << M));
}
| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ What language is this? \$\endgroup\$ – Nathan Osman Feb 7 '11 at 4:04
  • 3
    \$\begingroup\$ Can't you C? ;) \$\endgroup\$ – st0le Feb 7 '11 at 10:00
3
\$\begingroup\$

Uh, guys, in pretty much any language, it would be

N & (1 << M  - 1)
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Except M should be B and you forgot the code to read the input and loop through each case and write out the answer \$\endgroup\$ – gnibbler Feb 7 '11 at 5:24
  • 3
    \$\begingroup\$ @gnibbler, I think the point is that's it's a super-boring question. \$\endgroup\$ – Peter Taylor Feb 7 '11 at 10:17
  • \$\begingroup\$ @Peter, super-boring is rot13 or reversing stdin. This question isn't that bad by comparison \$\endgroup\$ – gnibbler Feb 7 '11 at 10:23
  • \$\begingroup\$ @gnibbler, it's on a par with factorial, and I don't think those two are separated from rot13 by more than a hair. Reversing stdin requires using a stack in most languages, but even so I don't think it's a worthwhile question either. \$\endgroup\$ – Peter Taylor Feb 7 '11 at 15:36
  • \$\begingroup\$ I don't think it's boring, I just think there's a canonically correct answer to the underlying math problem. The problems around looping and printing are boring, or at least pointless, because that's not the way coding challenges present themselves in real life. \$\endgroup\$ – Malvolio Feb 7 '11 at 17:07
1
\$\begingroup\$

Perl, 31

<>;/ /,say($`&~(-1<<$'))while<>

Perl 5.10 or later, run with perl -E '<code here>'

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Java

With whitespace to make readable:

long F(long M, long N) {
  M = 2<<M;
  while(N>=M) N-=M;
  return N;
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ That would be too slow. :) \$\endgroup\$ – fR0DDY Feb 4 '11 at 10:16
  • 1
    \$\begingroup\$ @fR0DDY You didn't specify any time constraints. \$\endgroup\$ – moinudin Feb 5 '11 at 12:09
  • \$\begingroup\$ @marcog Ya! I am sorry about that. \$\endgroup\$ – fR0DDY Feb 5 '11 at 12:41
  • \$\begingroup\$ Java (if I remember correctly). \$\endgroup\$ – Daniel Jun 10 '16 at 16:29
0
\$\begingroup\$

Racket (scheme) 29 bytes

Kinda cheating because racket doesn't even have the % operator:

(λ(n m)(modulo n(expt 2 m)))
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

J, 15 12 9 bytes

6 bytes thanks to @miles.

#.@#:~#&2

Previous 12-byte version

#.@({.~-)~#:

Usage

>> f =: #.@({.~-)~#:
>> 6 f 150
<< 22

Where >> is STDIN and << is STDOUT.

Explanation

#: converts n to base 2.

({.~-)~ then takes the last m digits from it

#. converts it back to base 2.

Previous 15-byte version:

2#.(0-[){.[:#:]

Usage

>> f =: 2#.(0-[){.[:#:]
>> 6 f 150
<< 22

Where >> is STDIN and << is STDOUT.

Explanation

[:#:] converts n to base 2.

(0-[){. then takes the last m digits from it

2#. converts it back to base 2.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Using hooks, I've got #.@({.~-)~#: for 12 bytes. \$\endgroup\$ – miles Jun 9 '16 at 1:12
  • \$\begingroup\$ Isn't the #. dyadic here? \$\endgroup\$ – Leaky Nun Jun 9 '16 at 1:15
  • \$\begingroup\$ No, it is used afterwards. For example, x f@g y = f (x g y) but something like x f&g y = (g x) f (g y). \$\endgroup\$ – miles Jun 9 '16 at 1:18
  • \$\begingroup\$ Another approach is #.@#:~#&2 for 9 bytes which creates k copies of 2 and uses that to create a base 2 representation of n for the last k binary digits, and converts it back to base 10. Used as 150 (#.@#:~#&2) 6 which outputs 22. \$\endgroup\$ – miles Jun 10 '16 at 23:47
  • \$\begingroup\$ Why don't you post that as a separate answer :) \$\endgroup\$ – Leaky Nun Jun 11 '16 at 0:59
0
\$\begingroup\$

SmileBASIC, 36 characters

INPUT N,M?N AND(1<<M)-1

There's basically only one solution to this...

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.