Statistics

Problem Statement for "EllysXors"

Problem Statement

XOR problems became very popular in TopCoder recently. (If you do not know the bitwise operation XOR, see the Notes section for an explanation.) That's why Elly decided to invent one of her own. Fortunately for you, the one she came up with is quite simple. You are given two longs L and R. She wants you to find the XOR of all numbers between L and R, inclusive.

Definition

Class:
EllysXors
Method:
getXor
Parameters:
long, long
Returns:
long
Method signature:
long getXor(long L, long R)
(be sure your method is public)

Notes

  • XOR (exclusive or) is a binary operation, performed on two numbers in binary notation. First, the shorter number is prepended with leading zeroes until both numbers have the same number of digits (in binary). Then, the result is calculated as follows: for each bit where the numbers differ the result has 1 in its binary representation. It has 0 in all other positions.
  • For example 42 XOR 7 is performed as follows. First, the numbers are converted to binary: 42 is 101010 and 7 is 111. Then the shorter number is prepended with leading zeros until both numbers have the same number of digits. This means 7 becomes 000111. Then 101010 XOR 000111 = 101101 (the result has ones only in the positions where the two numbers differ). Then the result can be converted back to decimal notation. In this case 101101 = 45, so 42 XOR 7 = 45.
  • One of the ways to calculate the XOR of more than two numbers A1, A2, ..., An is "A1 XOR (A2 XOR (... XOR An))..))". Since the function is commutative and associative, you can also express it as "A1 XOR A2 XOR ... XOR An" and group the operands in any way you like.
  • It can be proved that the answer is always less than 2*R for the given constraints.

Constraints

  • L and R will be between 1 and 4,000,000,000, inclusive.
  • L will be less than or equal to R.

Examples

  1. 3

    10

    Returns: 8

    ((((((3 XOR 4) XOR 5) XOR 6) XOR 7) XOR 8) XOR 9) XOR 10 = (((((7 XOR 5) XOR 6) XOR 7) XOR 8) XOR 9) XOR 10 = ((((2 XOR 6) XOR 7) XOR 8) XOR 9) XOR 10 = (((4 XOR 7) XOR 8) XOR 9) XOR 10 = ((3 XOR 8) XOR 9) XOR 10 = (11 XOR 9) XOR 10 = 2 XOR 10 = 8.

  2. 5

    5

    Returns: 5

    The XOR of a single number is the number itself.

  3. 13

    42

    Returns: 39

    A bit larger example.

  4. 666

    1337

    Returns: 0

    The answer can be zero.

  5. 1234567

    89101112

    Returns: 89998783

  6. 19

    113

    Returns: 18

  7. 42

    666

    Returns: 666

  8. 42

    1337

    Returns: 0

  9. 123456

    7891011

    Returns: 0

  10. 1000001

    10000001

    Returns: 1000001

  11. 12345678

    910111213

    Returns: 0

  12. 1000000000

    1000000000

    Returns: 1000000000

  13. 1

    2000000000

    Returns: 2000000000

  14. 1

    1

    Returns: 1

  15. 1

    2

    Returns: 3

  16. 1

    3

    Returns: 0

  17. 1

    4

    Returns: 4

  18. 2

    3

    Returns: 1

  19. 3

    4

    Returns: 7

  20. 2

    4

    Returns: 5

  21. 4

    8

    Returns: 8

  22. 2

    536879812

    Returns: 536879813

  23. 536879912

    999999999

    Returns: 0

  24. 2

    999999999

    Returns: 1

  25. 32

    32768

    Returns: 32768

  26. 31

    32768

    Returns: 32799

  27. 31

    32769

    Returns: 30

  28. 32

    32767

    Returns: 0

  29. 131071

    536870911

    Returns: 131071

  30. 131071

    536870912

    Returns: 537001983

  31. 131071

    536870913

    Returns: 131070

  32. 131072

    536870911

    Returns: 0

  33. 131072

    536870912

    Returns: 536870912

  34. 131072

    536870913

    Returns: 1

  35. 131073

    536870911

    Returns: 131072

  36. 131073

    536870912

    Returns: 537001984

  37. 131073

    536870913

    Returns: 131073

  38. 1048575

    1048575

    Returns: 1048575

  39. 1048576

    1048576

    Returns: 1048576

  40. 1048577

    1048577

    Returns: 1048577

  41. 32768

    131072

    Returns: 131072

  42. 1

    4000000000

    Returns: 4000000000

  43. 2

    4000000000

    Returns: 4000000001

  44. 3

    4000000000

    Returns: 4000000003

  45. 4

    4000000000

    Returns: 4000000000

  46. 1

    3500000000

    Returns: 3500000000

  47. 2

    3500000000

    Returns: 3500000001

  48. 3

    3500000000

    Returns: 3500000003

  49. 4

    3500000000

    Returns: 3500000000

  50. 1

    3200000000

    Returns: 3200000000

  51. 2

    3200000000

    Returns: 3200000001

  52. 3

    3200000000

    Returns: 3200000003

  53. 4

    3200000000

    Returns: 3200000000

  54. 666666666

    4000000000

    Returns: 4000000001

  55. 424242

    3333333333

    Returns: 0

  56. 3450000000

    3550000000

    Returns: 3550000000

  57. 3499999999

    3500000001

    Returns: 3499999998

  58. 3199999999

    3200000001

    Returns: 3199999998

  59. 1500000000

    3200000000

    Returns: 3200000000

  60. 1424242424

    3666666666

    Returns: 3666666667

  61. 130263043

    1177443348

    Returns: 1106113559

  62. 2810981134

    3499790709

    Returns: 0

  63. 2527172019

    3461657195

    Returns: 2527172019

  64. 354992550

    1606742078

    Returns: 1606742078

  65. 1472309589

    2224059869

    Returns: 1472309589

  66. 867820671

    3985937175

    Returns: 867820671

  67. 1897956893

    3035443472

    Returns: 3318593292

  68. 283975837

    933770122

    Returns: 658838295

  69. 3476788076

    3989990996

    Returns: 3989990996

  70. 2595773870

    3624559114

    Returns: 3624559114

  71. 2418495253

    2699053630

    Returns: 818349355

  72. 42960118

    1195813117

    Returns: 0

  73. 842199711

    1659595305

    Returns: 842199710

  74. 1332287090

    1496579640

    Returns: 1496579641

  75. 818324723

    2890422175

    Returns: 818324723

  76. 687152474

    1522117401

    Returns: 0

  77. 566218496

    1053716812

    Returns: 1053716812

  78. 449420940

    1946669556

    Returns: 1946669556

  79. 1864309337

    2771931311

    Returns: 1864309336

  80. 3094639439

    3984867497

    Returns: 3094639438

  81. 314517004

    2425746086

    Returns: 2425746087

  82. 1470596795

    1996872890

    Returns: 547510784

  83. 218065286

    2019768625

    Returns: 0

  84. 1948518086

    3594405127

    Returns: 1

  85. 504951108

    2187256312

    Returns: 2187256312

  86. 2844596960

    3124633025

    Returns: 1

  87. 1146426417

    3222714612

    Returns: 2219027652

  88. 34113053

    2366099053

    Returns: 34113053

  89. 852398326

    2876863866

    Returns: 2876863866

  90. 16232468

    3892549222

    Returns: 3892549223

  91. 1016421603

    3857091265

    Returns: 1016421602

  92. 76576982

    3185129678

    Returns: 3185129678

  93. 1501742132

    3477813612

    Returns: 3477813612

  94. 730722278

    2708003158

    Returns: 2708003158

  95. 75611648

    3307123408

    Returns: 3307123408

  96. 1275177872

    1591680236

    Returns: 1591680236

  97. 3394542013

    3526959612

    Returns: 409843776

  98. 3214926694

    3349611794

    Returns: 3349611794

  99. 2500973784

    3499081632

    Returns: 3499081632

  100. 1017144259

    3881433164

    Returns: 3690568591

  101. 13

    3452523424

    Returns: 3452523436

  102. 123

    4000000000

    Returns: 4000000123

  103. 123

    3999999996

    Returns: 3999999879

  104. 1

    1000000000

    Returns: 1000000000

  105. 40

    4000000000

    Returns: 4000000000

  106. 1

    3009710000

    Returns: 3009710000

  107. 3

    3999999997

    Returns: 2

  108. 1

    3999999999

    Returns: 0

  109. 1

    3999999998

    Returns: 3999999999

  110. 8

    3998899879

    Returns: 0

  111. 4325

    3906300000

    Returns: 3906304132

  112. 1

    2147483648

    Returns: 2147483648

  113. 2

    3000000000

    Returns: 3000000001

  114. 1

    3333333333

    Returns: 1

  115. 2

    3999999988

    Returns: 3999999989

  116. 268435456

    400000000

    Returns: 400000000

  117. 2147483647

    2147483648

    Returns: 4294967295

  118. 4000000000

    4000000000

    Returns: 4000000000

  119. 1

    3000000000

    Returns: 3000000000

  120. 9

    2147483647

    Returns: 8

  121. 17

    3654879452

    Returns: 3654879436

  122. 12325

    3987654236

    Returns: 3987666552

  123. 2

    3999999999

    Returns: 1

  124. 2900000000

    3989929292

    Returns: 3989929292

  125. 2

    3242432545

    Returns: 0

  126. 3221225470

    3221225472

    Returns: 3221225473

  127. 3999999987

    3999999999

    Returns: 3999999987

  128. 5

    3999999997

    Returns: 5

  129. 199

    3456789054

    Returns: 3456789240

  130. 1234567890

    2345678912

    Returns: 2345678913

  131. 3000000000

    4000000000

    Returns: 4000000000

  132. 10000000

    4000000000

    Returns: 4000000000

  133. 1

    999999999

    Returns: 0

  134. 1

    3348991222

    Returns: 3348991223

  135. 1287226651

    1779211297

    Returns: 1287226650

  136. 3723

    3999999999

    Returns: 3723

  137. 3990000000

    4000000000

    Returns: 4000000000

  138. 1253834751

    1253900287

    Returns: 1253834751

  139. 5

    999999999

    Returns: 4

  140. 1073741234

    3023435619

    Returns: 1

  141. 1

    400000000

    Returns: 400000000

  142. 1234567891

    2345678914

    Returns: 3259382416

  143. 3999999999

    3999999999

    Returns: 3999999999

  144. 3376367013

    3814610059

    Returns: 3376367012

  145. 1234567

    3912345678

    Returns: 3911417544

  146. 3800000

    4000000

    Returns: 4000000

  147. 2147483648

    2147483648

    Returns: 2147483648

  148. 9

    3999999998

    Returns: 3999999991

  149. 1

    11

    Returns: 0

  150. 2147483648

    4000000000

    Returns: 4000000000

  151. 1999999999

    3999999998

    Returns: 2573120512

  152. 1

    1999999999

    Returns: 0

  153. 3999000999

    3999000999

    Returns: 3999000999

  154. 3123456789

    3123456791

    Returns: 3123456788

  155. 3900000000

    3932753940

    Returns: 3932753940

  156. 4

    300234003

    Returns: 0

  157. 2

    2

    Returns: 2

  158. 3999999992

    4000000000

    Returns: 4000000000

  159. 1531682046

    2905690008

    Returns: 2905690009

  160. 3994584896

    4000000000

    Returns: 4000000000

  161. 362124

    455288

    Returns: 455288

  162. 4

    5

    Returns: 1

  163. 2000000000

    4000000000

    Returns: 4000000000

  164. 19288744

    1998894898

    Returns: 1998894899

  165. 512

    1024

    Returns: 1024

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: