diff --git a/inc/qcbor/qcbor_decode.h b/inc/qcbor/qcbor_decode.h
index bf4a042..e9c40fc 100644
--- a/inc/qcbor/qcbor_decode.h
+++ b/inc/qcbor/qcbor_decode.h
@@ -291,6 +291,16 @@
 /** Type for a double floating-point number. Data is in @c val.double. */
 #define QCBOR_TYPE_DOUBLE        27
 
+/** Special type for integers between -2^63 - 1 to -2^64 that
+ * can't be returned as @ref QCBOR_TYPE_INT64 because they don't fit
+ * in an int64_t. The value is returned in @c val.uint64, but this
+ * isn't the number transmitted. Do this arithmatic (carefully to
+ * avoid over/underflow) to get the value transmitted: - val.uint64 - 1.
+ * See QCBOREncode_AddNegativeUInt64() for a longer explanation
+ * and warning. */
+#define QCBOR_TYPE_65BIT_NEG_INT 28
+
+
 #define QCBOR_TYPE_BREAK         31 /* Used internally; never returned */
 
 /** For @ref QCBOR_DECODE_MODE_MAP_AS_ARRAY decode mode, a map that is
diff --git a/inc/qcbor/qcbor_encode.h b/inc/qcbor/qcbor_encode.h
index 6012b25..0aa28f6 100644
--- a/inc/qcbor/qcbor_encode.h
+++ b/inc/qcbor/qcbor_encode.h
@@ -544,6 +544,51 @@
 
 
 /**
+ * @brief Add a negative 64-bit integer to encoded output
+ *
+ * @param[in] pCtx  The encoding context to add the integer to.
+ * @param[in] uNum  The integer to add.
+ *
+ * QCBOREncode_AddInt64() is much better to encode negative integers
+ * than this.  What this can do is add integers with one more
+ * significant bit than an int64_t (a "65-bit" integer if you count
+ * the sign as a bit) which is possible because CBOR happens to
+ * support such integers.
+ *
+ * The actual value encoded is -uNum - 1. That is, give 0 for uNum to
+ * transmit -1, give 1 to transmit -2 and give UINT64_MAX to transmit
+ * -UINT64_MAX-1 (18446744073709551616). The interface is odd like
+ * this so all negative values CBOR can represent can be encoded by
+ * QCBOR (making this a complete CBOR implementation).
+ *
+ * The most negative value QCBOREncode_AddInt64() can encode is
+ * -9223372036854775808 which is -2^63 or negative
+ * 0x800000000000.  This can encode from -9223372036854775809 to
+ * -18446744073709551616 or -2^63 - 1 to -2^64. Note that
+ * it is not possible to represent plus or minus 18446744073709551616
+ * in any standard C data type.
+ *
+ * Negative integers are normally decoded in QCBOR with type
+ * @ref QCBOR_TYPE_INT64.  Integers in the range of -9223372036854775809
+ * to -18446744073709551616 are returned as @ref QCBOR_TYPE_65BIT_NEG_INT.
+ *
+ * WARNING: some CBOR decoders will be unable to decode -2^63 - 1 to
+ * -2^64.  Also, most CPUs do not have registers that can represent
+ * this range.  If you need 65-bit negative integers, you likely need
+ * negative 66, 67 and 68-bit negative integers so it is likely better
+ * to use CBOR big numbers where you can have any number of bits. See
+ * QCBOREncode_AddTNegativeBignum() and TODO: also xxxx
+ */
+void
+QCBOREncode_AddNegativeUInt64(QCBOREncodeContext *pCtx, uint64_t uNum);
+
+static void
+QCBOREncode_AddNegativeUInt64ToMap(QCBOREncodeContext *pCtx, const char *szLabel, uint64_t uNum);
+
+static void
+QCBOREncode_AddNegativeUInt64ToMapN(QCBOREncodeContext *pCtx, int64_t nLabel, uint64_t uNum);
+
+/**
  * @brief  Add a UTF-8 text string to the encoded output.
  *
  * @param[in] pCtx   The encoding context to add the text to.
@@ -2458,6 +2503,24 @@
 
 
 static inline void
+QCBOREncode_AddNegativeUInt64ToMap(QCBOREncodeContext *pMe, const char *szLabel, uint64_t uNum)
+{
+   /* Use _AddBuffer() because _AddSZString() is defined below, not above */
+   QCBOREncode_Private_AddBuffer(pMe,
+                                 CBOR_MAJOR_TYPE_TEXT_STRING,
+                                 UsefulBuf_FromSZ(szLabel));
+   QCBOREncode_AddNegativeUInt64(pMe, uNum);
+}
+
+static inline void
+QCBOREncode_AddNegativeUInt64ToMapN(QCBOREncodeContext *pMe, int64_t nLabel, uint64_t uNum)
+{
+   QCBOREncode_AddInt64(pMe, nLabel);
+   QCBOREncode_AddNegativeUInt64(pMe, uNum);
+}
+
+
+static inline void
 QCBOREncode_AddText(QCBOREncodeContext *pMe, const UsefulBufC Text)
 {
    QCBOREncode_Private_AddBuffer(pMe, CBOR_MAJOR_TYPE_TEXT_STRING, Text);
diff --git a/src/qcbor_decode.c b/src/qcbor_decode.c
index 693152f..332314b 100644
--- a/src/qcbor_decode.c
+++ b/src/qcbor_decode.c
@@ -884,10 +884,8 @@
          pDecodedItem->uDataType = QCBOR_TYPE_INT64;
 
       } else {
-         /* C can't represent a negative integer in this range so it
-          * is an error.
-          */
-         uReturn = QCBOR_ERR_INT_OVERFLOW;
+         pDecodedItem->val.uint64 = uArgument;
+         pDecodedItem->uDataType  = QCBOR_TYPE_65BIT_NEG_INT;
       }
    }
 
@@ -4921,6 +4919,12 @@
          }
          break;
 
+      case QCBOR_TYPE_65BIT_NEG_INT:
+         /* This type occurs if the value won't fit into int64_t
+          * so this is always an error. */
+         return QCBOR_ERR_CONVERSION_UNDER_OVER_FLOW;
+         break;
+
       default:
          return  QCBOR_ERR_UNEXPECTED_TYPE;
    }
@@ -5291,12 +5295,15 @@
 
       case QCBOR_TYPE_UINT64:
          if(uConvertTypes & QCBOR_CONVERT_TYPE_XINT64) {
-            *puValue =  pItem->val.uint64;
+            *puValue = pItem->val.uint64;
          } else {
             return QCBOR_ERR_UNEXPECTED_TYPE;
          }
          break;
 
+      case QCBOR_TYPE_65BIT_NEG_INT:
+         return QCBOR_ERR_NUMBER_SIGN_CONVERSION;
+
       default:
          return QCBOR_ERR_UNEXPECTED_TYPE;
    }
@@ -5634,6 +5641,10 @@
          return QCBOR_ERR_HW_FLOAT_DISABLED;
 #endif /* QCBOR_DISABLE_FLOAT_HW_USE */
 
+      case QCBOR_TYPE_65BIT_NEG_INT:
+         *pdValue = -(double)pItem->val.uint64 - 1;
+         break;
+
       default:
          return QCBOR_ERR_UNEXPECTED_TYPE;
    }
diff --git a/src/qcbor_encode.c b/src/qcbor_encode.c
index 146253d..a2a944a 100644
--- a/src/qcbor_encode.c
+++ b/src/qcbor_encode.c
@@ -665,6 +665,18 @@
 
 
 /*
+ * Public functions for adding negative integers. See qcbor/qcbor_encode.h
+ */
+void QCBOREncode_AddNegativeUInt64(QCBOREncodeContext *pMe, const uint64_t uValue)
+{
+   // TODO: Error out in dCBOR mode
+   QCBOREncode_Private_AppendCBORHead(pMe, CBOR_MAJOR_TYPE_NEGATIVE_INT, uValue, 0);
+
+   QCBOREncode_Private_IncrementMapOrArrayCount(pMe);
+}
+
+
+/*
  * Public functions for adding signed integers. See qcbor/qcbor_encode.h
  */
 void
@@ -676,9 +688,9 @@
    if(nNum < 0) {
       /* In CBOR -1 encodes as 0x00 with major type negative int.
        * First add one as a signed integer because that will not
-       * overflow. Then change the sign as needed for encoding.  (The
+       * overflow. Then change the sign as needed for encoding (the
        * opposite order, changing the sign and subtracting, can cause
-       * an overflow when encoding INT64_MIN. */
+       * an overflow when encoding INT64_MIN). */
       int64_t nTmp = nNum + 1;
       uValue = (uint64_t)-nTmp;
       uMajorType = CBOR_MAJOR_TYPE_NEGATIVE_INT;
diff --git a/test/qcbor_decode_tests.c b/test/qcbor_decode_tests.c
index 05d2466..b489657 100644
--- a/test/qcbor_decode_tests.c
+++ b/test/qcbor_decode_tests.c
@@ -116,7 +116,9 @@
  */
 
 static const uint8_t spExpectedEncodedInts[] = {
-   0x98, 0x2f, 0x3b, 0x7f, 0xff, 0xff, 0xff, 0xff,
+   0x98, 0x31, 0x3b, 0xff, 0xff, 0xff, 0xff, 0xff,
+   0xff, 0xff, 0xff, 0x3b, 0xFf, 0xff, 0xff, 0xff, 0xff,
+   0xff, 0xff, 0xfe, 0x3b, 0x7f, 0xff, 0xff, 0xff, 0xff,
    0xff, 0xff, 0xff, 0x3b, 0x00, 0x00, 0x00, 0x01,
    0x00, 0x00, 0x00, 0x00, 0x3a, 0xff, 0xff, 0xff,
    0xff, 0x3a, 0xff, 0xff, 0xff, 0xfe, 0x3a, 0xff,
@@ -156,6 +158,18 @@
 
    if((nCBORError = QCBORDecode_GetNext(pDCtx, &Item)))
       return (int32_t)nCBORError;
+   if(Item.uDataType != QCBOR_TYPE_65BIT_NEG_INT ||
+      Item.val.uint64 != 18446744073709551615ULL)
+      return -1;
+
+   if((nCBORError = QCBORDecode_GetNext(pDCtx, &Item)))
+      return (int32_t)nCBORError;
+   if(Item.uDataType != QCBOR_TYPE_65BIT_NEG_INT ||
+      Item.val.uint64 != 18446744073709551614ULL)
+      return -1;
+
+   if((nCBORError = QCBORDecode_GetNext(pDCtx, &Item)))
+      return (int32_t)nCBORError;
    if(Item.uDataType != QCBOR_TYPE_INT64 ||
       Item.val.int64 != -9223372036854775807LL - 1)
       return -1;
@@ -471,14 +485,6 @@
 }
 
 
-/* One less than the smallest negative integer allowed in C. Decoding
-   this should fail.
-   -9223372036854775809
- */
-static const uint8_t spTooSmallNegative[] = {
-   0x3b, 0x80, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
-};
-
 
 /*
    Tests the decoding of lots of different integers sizes
@@ -499,16 +505,6 @@
       return nReturn;
    }
 
-   // The one large negative integer that can be parsed
-   QCBORDecode_Init(&DCtx,
-                    UsefulBuf_FROM_BYTE_ARRAY_LITERAL(spTooSmallNegative),
-                    QCBOR_DECODE_MODE_NORMAL);
-
-   QCBORItem item;
-   if(QCBORDecode_GetNext(&DCtx, &item) != QCBOR_ERR_INT_OVERFLOW) {
-      nReturn = -4000;
-   }
-
    return(nReturn);
 }
 
@@ -5655,13 +5651,12 @@
  */
 static const uint8_t spRecoverableMapErrors[] = {
 #ifndef QCBOR_DISABLE_TAGS
-   0xa6,
+   0xa5,
    0x04, 0xc1, 0xfb, 0x7e, 0x37, 0xe4, 0x3c, 0x88, 0x00, 0x75, 0x9c,
    0x01, 0xd8, 0xe0, 0xd8, 0xe1, 0xd8, 0xe2, 0xd8, 0xe3, 0xd8, 0x04, 0x00,
 #else
    0xa4,
 #endif
-   0x03, 0x3b, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
    0x05, 0x00,
    0x05, 0x00,
    0x08, 0x08,
@@ -6050,12 +6045,6 @@
 #endif
 
 
-   QCBORDecode_GetInt64InMapN(&DCtx, 0x03, &nInt);
-   uErr = QCBORDecode_GetAndResetError(&DCtx);
-   if(uErr != QCBOR_ERR_INT_OVERFLOW) {
-      return 2023;
-   }
-
 #ifndef QCBOR_DISABLE_TAGS
    QCBORDecode_GetEpochDateInMapN(&DCtx, 0x04, QCBOR_TAG_REQUIREMENT_TAG, &nInt);
    uErr = QCBORDecode_GetAndResetError(&DCtx);
@@ -6561,8 +6550,8 @@
       FLOAT_ERR_CODE_NO_FLOAT_HW(QCBOR_SUCCESS)
    },
    {
-      "Negative integer -18446744073709551616",
-      {(uint8_t[]){0x3b, 0x7f, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff }, 9},
+      "Negative integer -9223372036854775808",
+      {(uint8_t[]){0x3b, 0x7f, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff}, 9},
       -9223372036854775807-1, // INT64_MIN
       QCBOR_SUCCESS,
       0ULL,
@@ -6571,6 +6560,16 @@
       FLOAT_ERR_CODE_NO_FLOAT_HW(QCBOR_SUCCESS)
    },
    {
+      "Negative integer -18446744073709551616",
+      {(uint8_t[]){0x3b, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff}, 9},
+      0ULL,
+      QCBOR_ERR_CONVERSION_UNDER_OVER_FLOW,
+      0ULL,
+      QCBOR_ERR_NUMBER_SIGN_CONVERSION,
+      -18446744073709551616.0,
+      FLOAT_ERR_CODE_NO_FLOAT_HW(QCBOR_SUCCESS)
+   },
+   {
       "Double Floating point value 100.3",
       {(uint8_t[]){0xfb, 0x40, 0x59, 0x13, 0x33, 0x33, 0x33, 0x33, 0x33}, 9},
       100L,
diff --git a/test/qcbor_encode_tests.c b/test/qcbor_encode_tests.c
index 0abbb72..5b8c071 100644
--- a/test/qcbor_encode_tests.c
+++ b/test/qcbor_encode_tests.c
@@ -276,10 +276,10 @@
 
 
 static const uint8_t spExpectedEncodedAll[] = {
- 0x98, 0x23, 0x66, 0x55, 0x49, 0x4e, 0x54, 0x36, 0x32, 0xd8,
+ 0x98, 0x24, 0x66, 0x55, 0x49, 0x4e, 0x54, 0x36, 0x32, 0xd8,
  0x64, 0x1a, 0x05, 0x5d, 0x23, 0x15, 0x65, 0x49, 0x4e, 0x54,
  0x36, 0x34, 0xd8, 0x4c, 0x1b, 0x00, 0x00, 0x00, 0x12, 0x16,
- 0xaf, 0x2b, 0x15, 0x00, 0x38, 0x2b, 0xa4, 0x63, 0x4c, 0x42,
+ 0xaf, 0x2b, 0x15, 0x00, 0x38, 0x2b, 0x20, 0xa4, 0x63, 0x4c, 0x42,
  0x4c, 0x18, 0x4d, 0x23, 0x18, 0x58, 0x78, 0x1a, 0x4e, 0x45,
  0x47, 0x4c, 0x42, 0x4c, 0x54, 0x48, 0x41, 0x54, 0x20, 0x49,
  0x53, 0x20, 0x4b, 0x49, 0x4e, 0x44, 0x20, 0x4f, 0x46, 0x20,
@@ -521,8 +521,9 @@
    QCBOREncode_AddSZString(pECtx, "INT64");
    QCBOREncode_AddTag(pECtx, 76);
    QCBOREncode_AddInt64(pECtx, 77689989909);
-   QCBOREncode_AddUInt64(pECtx,0);
+   QCBOREncode_AddUInt64(pECtx, 0);
    QCBOREncode_AddInt64(pECtx, -44);
+   QCBOREncode_AddNegativeUInt64(pECtx, 0);
 
    /* ints that go in maps */
    QCBOREncode_OpenMap(pECtx);
@@ -695,7 +696,7 @@
 
    QCBOREncode_Init(&ECtx, UsefulBuf_FROM_BYTE_ARRAY(spBigBuf));
 
-   AddAll (&ECtx);
+   AddAll(&ECtx);
 
    UsefulBufC Enc;
    if(QCBOREncode_Finish(&ECtx, &Enc)) {